牛客集训第七场J /// DP

题目大意：

在矩阵（只有52种字符）中找出所有不包含重复字符的子矩阵个数

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n,m;
char G[1005][1005];
int lr[1005][1005], ud[1005][1005];
int pos[100], len[1005];

int main()
{
    while(~scanf("%d%d",&n,&m)) {
        for(int i=1;i<=n;i++) scanf("%s",G[i]+1);
        for(int i=1;i<=n;i++) {
            memset(pos,0,sizeof(pos));
            for(int j=1;j<=m;j++) {
                lr[i][j]=min(lr[i][j-1]+1,j-pos[G[i][j]-'A']);
                pos[G[i][j]-'A']=j;
            }
        }
        for(int j=1;j<=m;j++) {
            memset(pos,0,sizeof(pos));
            for(int i=1;i<=n;i++) {
                ud[i][j]=min(ud[i-1][j]+1,i-pos[G[i][j]-'A']);
                pos[G[i][j]-'A']=i;
            }
        }
        /*  若固定右下角
            且只看一个因素（长度或高度），忽略另一个因素
            则高度（长度）多大 划分方案就有多少种
            如高度（长度）为3 划分方案就恰好3种
            
            用一个极端的样例说明
            ABC 固定C为右下角的划分方案只有三种 
            即 C、BC、ABC 三种
        */
        ll ans=0; 
        for(int j=1;j<=m;j++) {
            memset(len,0,sizeof(len));
            for(int i=1;i<=n;i++) { /// 求以G[i][j]为右下角的划分方案
                    
                for(int k=0;k<lr[i][j];k++) { /// 在i行 j列（右界）向左k长度
                    len[k]=min(len[k]+1,ud[i][j-k]); // 控制高度
                    /// 由i-1行扩展而来有 len[k]+1 种划分 
                    /// 由i行j-k列（左界）控制的 ud[i][j-k] 高度，超过这个高度会有重复
                    // 不用纠结在左右界只间有更小的高度 这个问题会在 长度控制 时被制约到
                    /// 两者中取小 控制不重复
                    
                    if(k) len[k]=min(len[k],len[k-1]); // 控制长度
                    /// k长度的划分 不可能多于 k-1长度的划分
                    ans+=len[k];
                }
            
                for(int k=lr[i][j];k<54;k++) len[k]=0;
            }
        }
        printf("%lld
",ans);
    }

    return 0;
}