【CF1393】D. Rarity and New Dress（dp）

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

分析

如果仅考虑菱形的左上角那块三角，可以发现这是可以用$dp$来算出最大长度的，如果$(i?1,j)$以及$(i,j?1)$的颜色与$(i,j)$颜色相同，那么转移方程就为$dp[i][j]=min(dp[i?1][j],dp[i][j?1])+1$。
我们在四个方向上都做一遍，然后取个小就可以得出以每个点为中心的最大菱形半径。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define lson (k << 1)
#define rson (k << 1 | 1)const int INF = 0x3f3f3f3f;
const int N = 2e3 + 10;
const int M = 1e6 + 10;
const ll P = 1e9 + 7;int n, m;
char s[N][N];
int a[N][N], b[N][N], c[N][N], d[N][N], ans[N][N];
ll sum;int main() {
    scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%s",s[i] + 1);for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
    a[i][j] = 1;if(i - 1 >= 1 && s[i - 1][j] == s[i][j] && j - 1 >= 1 && s[i][j - 1] == s[i][j])a[i][j] = min(a[i - 1][j], a[i][j - 1]) + 1;}}for(int i=1;i<=n;i++){
    for(int j=m;j>=1;j--){
    b[i][j] = 1;if(i - 1 >= 1 && s[i - 1][j] == s[i][j] && j + 1 <= m && s[i][j + 1] == s[i][j])b[i][j] = min(b[i - 1][j], b[i][j + 1]) + 1;}}for(int i=n;i>=1;i--){
    for(int j=m;j>=1;j--){
    c[i][j] = 1;if(i + 1 <= n && s[i + 1][j] == s[i][j] && j + 1 <= m && s[i][j + 1] == s[i][j])c[i][j] = min(c[i + 1][j], c[i][j + 1]) + 1;}}for(int i=n;i>=1;i--){
    for(int j=1;j<=m;j++){
    d[i][j] = 1;if(i + 1 <= n && s[i + 1][j] == s[i][j] && j - 1 >= 1 && s[i][j - 1] == s[i][j])d[i][j] = min(d[i + 1][j], d[i][j - 1]) + 1;}}for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
    ans[i][j] = min({
    a[i][j], b[i][j], c[i][j], d[i][j]});sum += ans[i][j];}}printf("%lld\n",sum);return 0;
}