[codeforces 1393D] Rarity and New Dress 图形重叠+动归dp

Codeforces Round #662 (Div. 2)   参与排名人数13194

[codeforces 1393D]   Rarity and New Dress   图形重叠+动归dp

总目录详见https://blog.csdn.net/mrcrack/article/details/103564004

在线测评地址https://codeforces.com/contest/1393/problem/D

题目大意：由格子构成的一块布，有三种裁剪方式，一格一格的裁剪，十字架形式的裁剪，菱形形式的裁剪。给出一块布，问有几种裁剪形式的数量。

基本思路：一格一格的裁剪，可以单独计算，十字架形式的裁剪，是菱形形式的裁剪的基础，菱形形式的裁剪数量，可以通过动态规划过程进行计算。详见AC代码，以及下面的模拟过程。

图形重叠过程如下：

分解过程如下：

AC代码如下：

#include <cstdio>
#include <algorithm>
#define maxn 2010
using namespace std;
char s[maxn][maxn];
int dp[maxn][maxn];
int main(){int n,m,i,j,ans;scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%s",s[i]+1);ans=n*m;//单个格子的形式种类for(i=3;i<=n;i++)for(j=2;j+1<=m;j++){if(s[i][j]==s[i-2][j]&&s[i][j]==s[i-1][j-1]&&s[i][j]==s[i-1][j]&&s[i][j]==s[i-1][j+1]){dp[i][j]=min(dp[i-1][j-1],dp[i-2][j]);dp[i][j]=min(dp[i][j],dp[i-1][j]);dp[i][j]=min(dp[i][j],dp[i-1][j+1]);dp[i][j]+=1;}ans+=dp[i][j];}printf("%d\n",ans);return 0;
}