Codeforces Round #662 (Div. 2) D. Rarity and New Dress_综合

题目链接：D. Rarity and New Dress

昨天集训队一名同学在做这道题，为了给他增加信心，我说这题很简单，随便做做就过了，然后今天看了这道题，一下午没写出代码。。。emmm，只想在这对那位同学说声抱歉。

题意

给你一个n*m的网格，每个点有一个字母代表一种颜色，题目构造了一种图案——正菱形图案，图案内的颜色必须相同，单个字符也算一个正菱形。
问你在网格中符合条件的图案有多少个？

题解

首先我们来分析这道题，正菱形可以分为上三角形和下三角形，我们以格子的每个点为菱形中心，那么它对答案的贡献值为min(上三角层数，下三角层数)。其实三角形层数也是以(i,j)为中心所能扩展的正菱形个数。
上三角层数如何求？
通过分析得知上三角的层数等于该中点到最左边/最右边的数量。

${设l[i][j]:以(i,j)为中心，向左扩展最多扩展的个数}$
${设r[i][j]:以(i,j)为中心，向右扩展最多扩展的个数}$
${设mid[i][j]:以(i,j)为中心所能组成最大的三角形层数，也是向左/右扩展的个数}$

由上面易知状态转移方程
${l[i][j]=(g[i][j]==g[i][j-1]) ? l[i][j-1]+1:1; (g[i][j]为网格颜色)}$
${r[i][j]=(g[i][j]==g[i][j+1]) ? r[i][j+1]+1:1; (g[i][j]为网格颜色)}$
${mid[i][j]=min(l[i][j],r[i][j]);}$

知道了这些上三角数就很好求
${设up[i][j]:以(i,j)为上三角中心的最大层数}$

上三角的状态转移方程为：
${up[i][j]=(g[i][j]==g[i-1][j])?min(mid[i][j],up[i-1][j]+1):1 ;}$

同理下三角的状态转移方程为：
${down[i][j]=(g[i][j]==g[i+1][j])?min(mid[i][j],down[i+1][j]+1):1 ;}$

最终答案就是枚举每个点加上每个点的贡献值： ${min(up[i][j],down[i][j])}$

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
//extern "C"{void *__dso_handle=0;}
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define lowbit(x) x&-xconst double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=2005;
const int maxm=100+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);char g[maxn][maxn];
int l[maxn][maxn],r[maxn][maxn],up[maxn][maxn],down[maxn][maxn];
int mid[maxn][maxn];int main()
{ios;int n,m;cin >> n >> m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) cin >> g[i][j];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(g[i][j]==g[i][j-1]) l[i][j]=l[i][j-1]+1;else l[i][j]=1;}for(int j=m;j>=1;j--){if(g[i][j]==g[i][j+1]) r[i][j]=r[i][j+1]+1;else r[i][j]=1;mid[i][j]=min(l[i][j],r[i][j]);}}for(int j=1;j<=m;j++){for(int i=1;i<=n;i++){if(g[i][j]==g[i-1][j]) up[i][j]=min(mid[i][j],up[i-1][j]+1);else up[i][j]=1;}for(int i=n;i>=1;i--){if(g[i][j]==g[i+1][j]) down[i][j]=min(mid[i][j],down[i+1][j]+1);else down[i][j]=1;}}ll ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) ans+=min(up[i][j],down[i][j]);printf("%lld\n",ans);
}