https://www.nowcoder.com/acm/contest/145/J
题意：
让你求出有几个矩阵，他的行和列中的每个字母都不一样。注意 只要求一行中都不一样。
和一列中都不一样。
POINT：
预处理出一个点能往上，往左延伸的长度。
枚举矩阵的右下端点。
对于如何把n*m*52*52的效率优化一个52去掉。看代码注解
#include <bits/stdc++.h> using namespace std; #define LL long long const int N = 1022; char mp[N][N]; int lmax[N][N],umax[N][N],pos[N],len[N][N]; int n,m; LL solve() { for(int i=1;i<=n;i++){ memset(pos,0,sizeof pos); for(int j=1;j<=m;j++){ lmax[i][j]=min(lmax[i][j-1]+1,j-pos[mp[i][j]]); pos[mp[i][j]]=j; } } for(int j=1;j<=m;j++){ memset(pos,0,sizeof pos); for(int i=1;i<=n;i++){ umax[i][j]=min(umax[i-1][j]+1,i-pos[mp[i][j]]); pos[mp[i][j]]=i; } } LL ans=0; for(int j=1;j<=m;j++){ memset(len[1],0,sizeof len[1]); for(int i=1;i<=n;i++){ //确定了矩阵的右下角 //len[i][y]代表(i,j-y)到(i,j)这段区间往上最大能到多少. //可以开一维，因为都是从上一层推下来，不过这样比较好懂. for(int l=0;l<lmax[i][j];l++){ len[i][l]=min(umax[i][j-l],len[i-1][l]+1);//单纯(i,j-l)到(i,j)的区间可以往上到多少 if(l) len[i][l]=min(len[i][l],len[i][l-1]);//如果之前的更小，当然要取之前的。 ans+=len[i][l]; } for(int l=lmax[i][j];l<=52;l++) len[i][l]=0;//因为i,j这个点最大延伸到j-lmax+1。所以这之后的点和j形成的区间，往上只能是0 } } return ans; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",mp[i]+1); printf("%lld\n",solve()); return 0; }
