Codeforces Round #662 (Div. 2) D.Rarity and New Dress

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

题目链接：https://codeforces.com/contest/1393/problem/D

题意：
给你一个n*m的由字母组成的矩阵，，问你这个矩阵中有多少个“相同字母组成的菱形”，菱形规则看图更好理解

比赛的时候一直想着以中心点dp，因为中心点的菱形数量等于它上下左右菱形最大值加1（前提是它上下左右和它本身字符相同）。但是这个状态好像没办法转移，没有办法维护四周的dp值，所以比赛最后还是以失败告终。。。。
早上看到一个大佬的解法，恍然大悟，因为这个图形的特点，我们可以以最下的那个点来进行dp，
dp[i][j]表示以mp[i][j]这个点为最低点的菱形数量，那么我们就可以找出转移方程只和前面三个位置有关，并且后面的状态不会被破坏。
$d p [i] [j] = m i n (d p [i - 2] [j], d p [i - 1] [j - 1], d p [i - 1] [j + 1]) + 1$ ,还有相同字符的前提不要忘

/** @沉着，冷静！: 噗，这你都信！* @LastEditors: HANGNAG* @LastEditTime: 2020-08-08 10:27:38* @FilePath: \ACM_vscode\codeforces\cf.cpp*/#include<algorithm>
#include<string.h>
#include<iostream>
#include<stdio.h>
#include<string>
#include<math.h>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define emplace_back push_back
#define pb push_back
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int N = 2e3 + 10;
char mp[N][N];
LL dp[N][N];
int main()
{int n, m;scanf("%d%d", &n, &m);for (int i = 2; i <= n + 1;i++){scanf("%s", mp[i] + 1);}LL ans = 0;for (int i = 2; i <= n + 1;i++){for (int j = 1; j <= m;j++){if(mp[i][j]==mp[i-1][j]&&mp[i][j]==mp[i-2][j]&&mp[i][j]==mp[i-1][j-1]&&mp[i][j]==mp[i-1][j+1]){dp[i][j] = min(dp[i - 2][j], min(dp[i - 1][j - 1], dp[i - 1][j + 1])) + 1;}else{dp[i][j] = 1;}ans += dp[i][j];}}printf("%lld\n", ans);return 0;
}