D - Rarity and New Dress（二维 DP）

题目大概是从 n*m 的图中，找出菱形，菱形的形状由相同字母组成的题目中 涂绿 的形状  

首先想到的就是递推，以 ch[i][j]=‘a’ 为例：

以 [i][j] 为中心向上向下走，直到遇到不为 ‘a’ 的字符

在以 [i][j] 为中心向左向右走，直到遇到不为 'a' 的字符

取最小值作为以 ch[i][j] 为中心的贡献值

dp[i][j]=min(l[i][j],r[i][j],u[i][j],d[i][j])

dp[i][j]：以 ch[i][j] 为中心的贡献值

l[i][j]：ch[i][j] 左边有多少个字符与 ch[i][j] 相同

r[i][j]：ch[i][j] 右边边有多少个字符与 ch[i][j] 相同

u[i][j]：ch[i][j] 上边边有多少个字符与 ch[i][j] 相同

d[i][j]：ch[i][j] 下边有多少个字符与 ch[i][j] 相同

这样递推过去就可以了

WA 代码： 

const int N=2e3+5;int n,m,t;int i,j,k;int dp[N][N];char ch[N][N];int l[N][N],r[N][N];int u[N][N],d[N][N];int main()
{//IOS;while(~sdd(n,m)){ll ans=0;for(i=1;i<=n;i++){ss(ch[i]+1);      }for(i=1;i<=n;i++){for(j=1;j<=m;j++){if(i==1) u[i][j]=0,dp[i][j]=1;if(i==n) d[i][j]=0,dp[i][j]=1;if(j==1) l[i][j]=0,dp[i][j]=1;if(j==m) r[i][j]=0,dp[i][j]=1;if(dp[i][j]){ continue; } if(ch[i][j]==ch[i][j-1]) l[i][j]=l[i][j-1]+1;else l[i][j]=0;}for(j=m;j>=1;j--){if(ch[i][j]==ch[i][j+1]) r[i][j]=r[i][j+1]+1;else r[i][j]=0;}}for(j=1;j<=m;j++){for(i=1;i<=n;i++){if(ch[i][j]==ch[i-1][j]) u[i][j]=u[i-1][j]+1;else u[i][j]=0;}for(i=n;i>=1;i--){if(ch[i][j]==ch[i+1][j]) d[i][j]=d[i+1][j]+1;else d[i][j]=0;dp[i][j]=min(min(d[i][j],u[i][j]),min(r[i][j],l[i][j]))+1;ans+=1ll*dp[i][j];}}/*for(i=1;i<=n;i++){for(j=1;j<=m;j++){cout<<dp[i][j];}cout<<endl;}*/pll(ans);}//PAUSE;return 0;
}

上面的代码为什么会错…… 

想了好久，才想过来

假设图上标绿的圆点都是字符 'a' ，标绿的圆点为字符 'b'，中间标绿的原点坐标为 i,j

如果按照上述代码执行，其上下左右都有 2 个相同的字符相同，所以 dp[i][j]=2+1

但是图上很清楚，最外层无法构成

所以在递推 u[i][j] 时，不是简单的 u[i][j]=u[i-1][j]+1

而是变成 u[i][j]=min(u[i-1][j]+1,l[i][j],r[i][j])

这样为什么会成立呢？

因为 u[i-1][j]=min(u[i-2][j]+1,l[i-1][j],r[i-1][j])

这样 u 递推下来就避免了以上问题

从几何方面解释：

当某一点确定了水平方向的范围后，即 l[i][j] r[i][j] 确定后

其竖直方向的范围不得超过水平方向的范围

 AC 代码：

const int N=2e3+5;int n,m,t;int i,j,k;int dp[N][N];char ch[N][N];int l[N][N],r[N][N];int u[N][N],d[N][N];int main()
{//IOS;while(~sdd(n,m)){ll ans=0;for(i=1;i<=n;i++){ss(ch[i]+1);      }for(i=1;i<=n;i++){for(j=1;j<=m;j++){if(i==1) u[i][j]=0,dp[i][j]=1;if(i==n) d[i][j]=0,dp[i][j]=1;if(j==1) l[i][j]=0,dp[i][j]=1;if(j==m) r[i][j]=0,dp[i][j]=1;if(dp[i][j]){ continue; } if(ch[i][j]==ch[i][j-1]) l[i][j]=l[i][j-1]+1;else l[i][j]=0;}for(j=m;j>=1;j--){if(ch[i][j]==ch[i][j+1]) r[i][j]=r[i][j+1]+1;else r[i][j]=0;}}for(j=1;j<=m;j++){for(i=1;i<=n;i++){if(ch[i][j]==ch[i-1][j]) u[i][j]=min(u[i-1][j]+1,min(l[i][j],r[i][j]));else u[i][j]=0;}for(i=n;i>=1;i--){if(ch[i][j]==ch[i+1][j]) d[i][j]=min(d[i+1][j]+1,min(l[i][j],r[i][j]));else d[i][j]=0;dp[i][j]=min(d[i][j],u[i][j])+1 ;ans+=1ll*dp[i][j];}}pll(ans);}//PAUSE;return 0;
}