D. Rarity and New Dress【DP】【以一个点向上延伸的最长边长为DP】

D. Rarity and New Dress

题意

给出一个矩阵，求一下矩阵中类似图中斜方体的个数。

思路

DP：f[i] [j] :表示（i ， j）这个位置，往上可以延伸的最大斜方体的边长（不是高度）

那么f(i,j) = x就可以组合出来x种斜方体。

关于f(i,j) 的推导：f(i,j) 恰好是：（i-1,j-1) 、(i-1,j+1 ) 、(i,j-2) 这三个点的最小值。转移条件为：那四个点一样，

代码

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=1e6+100;
typedef long long ll;
typedef pair<int,int>pll;
ll f[3010][3010];
int n,m;
char a[3010][3010];
int main()
{cin>>n>>m;for(int i=2;i<=n+1;i++)scanf("%s",a[i]+1);for(int i=2;i<=n+1;i++)for(int j=1;j<=m;j++){if((a[i-1][j-1] == a[i][j]) && (a[i][j] == a[i-1][j] )&& (a[i][j] == a[i-1][j+1]) && (a[i][j]==a[i-2][j])) f[i][j]=min(min(f[i-1][j-1],f[i-1][j+1]),f[i-2][j]) +1;else f[i][j]=1;}ll res=0;// for(int i=2;i<=n+1;i++)// {//     for(int j=1;j<=m;j++)//         cout<<f[i][j]<<' ';//     cout<<endl;// }for(int i=2;i<=n+1;i++)for(int j=1;j<=m;j++)res+=f[i][j];cout<<res<<endl;return 0;
}