苏州企业如何建网站/南宁百度seo排名优化

同步于这里,来这里观看体验更差哦好哦

$预处理+DP$

先解释一下下面出现的三角形,尺寸是啥意思

尺寸为1的三角形s
尺寸为1的菱形s
尺寸为2的三角形s
sss
尺寸为2的菱形s
ssss
尺寸为3的三角形ssss
sssss
尺寸为3的菱形ssss
ssssssss s

$那每个菱形显然可以分为上三角和下三角拼成的$

$那么以这个格子为中心的最大菱形就是min(最大上三角,最大下三角)$

接下来就是dp最大上三角(下三角了)

$我们令l[i][j]表示(i,j)向左延伸的最大同色格子$

$r[i][j]表示(i,j)向右延伸的最大同色格子$

$mid[i][j]=min(l[i][j],r[i][j]),表示(i,j)为中心的一行最多作为哪个尺寸的三角$

$那么最大上三角的转移方程是,当上面的格子和自己同色时$

$$up[i][j]=min(up[i-1][j]+1,mid[i][j])$$

$up[i-1][j]表示接着上面的尺寸,自己这行再加大一个尺寸,但是不能超过mid[i][j]$

$当上面的格子和自己不同色时,up[i][j]=1$

下三角同理

#include <bits/stdc++.h>
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;
}