D. Rarity and New Dress(예비 처리 dp)

여기와 함께 이곳에 와서 보는 체험이 더 나빠요. 좋아요.
사전 처리 + D P 사전 처리 + DP 사전 처리 + DP
먼저 아래에 나타난 삼각형, 사이즈가 무슨 뜻인지 설명해 주세요.

   1    s
   1   s
   2    
 s
sss
   2   
 s
sss
 s
   3    
  s
 sss
sssss
   3   
  s
 sss
sssss
 sss 
  s

그 모든 마름모꼴은 분명히 상삼각형과 하삼각형으로 나눌 수 있다. 그 마름모꼴은 분명히 상삼각형과 하삼각형으로 나눌 수 있다.
그럼 이 칸을 중심으로 최대 마름모꼴이 mi n(최대 상삼각형, 최대 하삼각형)이면 이 칸을 중심으로 최대 마름모꼴이 min(최대 상삼각형, 최대 하삼각형)이면 이 칸을 중심으로 최대 마름모꼴이 min(최대 상삼각형, 최대 하삼각형)
다음은 dp 최대 상삼각형(하삼각형)
우리는 l[i][j]로 하여금 (i, j)왼쪽으로 뻗은 최대 동색 칸을 표시하고 l[i][j]로 하여금 (i, j)왼쪽으로 뻗은 최대 동색 칸을 표시하도록 한다. 우리는 l[i][j]로 (i, j)왼쪽으로 뻗은 최대 동색 칸을 표시한다.
r[i][j]는 (i, j) 오른쪽으로 뻗은 최대 동색 격자 r[i][j] 표시(i, j) 오른쪽으로 뻗은 최대 동색 격자 r[i][j] 표시(i, j) 오른쪽으로 뻗은 최대 동색 격자
m i d [i] [j] = m i n(l [i] [j], r [i] [j]), (i, j) 중심의 한 줄이 어느 사이즈로 가장 많은지를 나타내는 삼각mid [i] [j]=min(\l[i] [j], r[i] [j]\), (i, j) 중심의 한 줄이 어느 사이즈로 가장 많은지를 나타내는 삼각mid [i] [j]=min(l[i] [j], r[i] [j]), 어느 줄이 중심이 되는지, 어느 줄이 가장 많은 삼각 되는지
그러면 가장 큰 상삼각형의 전이 방정식은 위의 칸이 자신과 동색일 때 가장 큰 상삼각형의 전이 방정식은 위의 칸이 자신과 동색일 때 가장 큰 상삼각형의 전이 방정식은 위의 칸이 자신과 동색일 때
u p [ i ] [ j ] = m i n ( u p [ i − 1 ] [ j ] + 1 , m i d [ i ] [ j ] ) up[i][j]=min(up[i-1][j]+1,mid[i][j]) up[i][j]=min(up[i−1][j]+1,mid[i][j])
lp[i --1] [j]는 위에 있는 사이즈를 표시하고 자신의 이 줄에 있는 사이즈를 하나 더 늘리지만 mi d[i] [j] up [i-1] [j]는 위에 있는 사이즈를 표시하고 자신의 이 줄에 있는 사이즈를 하나 더 늘리지만mid[i] [j] up[i-1] [j]는 위에 있는 사이즈를 초과하면 안 된다는 뜻이다. 자신의 이 줄에 있는 사이즈를 하나 더 늘리면mid[i][j]를 초과해서는 안 된다는 뜻이다.
위의 칸이 자신과 다른 색일 때 up[i][j]=1 위의 칸이 자신과 다른 색일 때 up[i][j]=1 위의 칸이 자신과 다른 색일 때 up[i][j]=1
하삼각 동리

#include 
using namespace std;
const int maxn=2009;
char s[2009][2009];
int l[maxn][maxn],r[maxn][maxn],mid[maxn][maxn];
int n,m,up[maxn][maxn],down[maxn][maxn];
int main()
{
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
		cin >> s[i][j];	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			if( s[i][j]==s[i][j-1] )	l[i][j]=l[i][j-1]+1;
			else	l[i][j]=1;
		for(int j=m;j>=1;j--)
		{
			if( s[i][j]==s[i][j+1] )	r[i][j]=r[i][j+1]+1;
			else	r[i][j]=1;			
			mid[i][j]=min( l[i][j],r[i][j] );//     
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if( s[j][i]==s[j-1][i] )	
				up[j][i]=min( mid[j][i],up[j-1][i]+1 );
			else	up[j][i]=1;
		}
		for(int j=n;j>=1;j--)
		{
			if( s[j][i]==s[j+1][i] )	
				down[j][i]=min( mid[j][i],down[j+1][i]+1 );
			else	down[j][i]=1;			
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
		ans+=min(up[i][j],down[i][j]);
	cout << ans;
}