D. Rarity and New Dress（dp）

本文主要是介绍D. Rarity and New Dress（dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目传送门

题意： 给你一个由字母组成的宫格，问你宫格中有多少个由相同字母组成的“菱形”。
这三种是符合条件的：

这三种是不符合条件的：

思路： 赛中想到了是dp但是没有想出正确的状态转移方程。赛后发现，我们暂时把菱形的size定义为(n+1)/2，n是层数，那么我们发现，一个size为m的菱形，它的最下面那个点(i,j),那么(i-1,j-1) , (i-2,j) , (i-1,j+1) ，(i-1,j-1）
这四个点，一定size为m-1的菱形的最下面的点。所以我们就可以通过这个来dp。

代码：

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define endl '\n'
#define null NULL
#define ls p<<1
#define rs p<<1|1
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long
#define int long long
#define pii pair<int,int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pdd pair<double,double>
#define unmap unordered_map
#define all(x) x.begin(),x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
char *fs,*ft,buf[1<<20];
#define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++;
inline int read(){int x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();}
return x*f;}
using namespace std;
const int N=2e3+5;
const int inf=0x3f3f3f3f;
const int mod=998244353;
const double eps=1e-6;
const double PI=acos(-1);
char a[N][N];
int f[N][N];
signed main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];ll res=0;for(char ch='a';ch<='z';ch++){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]==ch)f[i][j]=1;elsef[i][j]=0;if(f[i][j])f[i][j]+=min(min(f[i-1][j-1],f[i-1][j]),min(i>=2?f[i-2][j]:0,f[i-1][j+1]));res+=f[i][j];}}}cout<<res<<endl;
}