[CF1181C] Flag - dp

Description

一面国旗可以抽象为一个 $ n\times m (n,m \le 1000)$ 的矩形，每一个位置有一个颜色。这个矩形由自上而下三条横向的颜色带组成，每一条颜色带宽度相等，而且相邻两个颜色带颜色不能相同。现在你有一个 $ n\times m $ 的矩形，你需要计算其中能够称为国旗的子矩形数量。

Solution

预处理 \(f[i][j]\) 表示以元素 \((i,j)\) 为顶端，在满足颜色相同的条件下，能向下延伸的最长距离

然后计算以每个点为右上角的 Flag 数量

对于单列的判断，只需要使用几个条件即可，判定位置 \(i+3d-1\) 合法，并且 \(i+d,i+2d\) 的 \(f\) 值满足条件

考虑复列，如果第 \(j\) 列与第 \(j-1\) 列的颜色对应相同，并且延伸数符合条件，则将计数器 \(+1\)，否则将计数器置 \(1\)

（用好题目条件来构造算法，简直太妙了）

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1005;

int n,m,f[N][N],a[N][N];

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        string s;
        cin>>s;
        for(int j=1;j<=m;j++) {
            a[i][j]=s[j-1]-‘a‘+1;
        }
    }
    for(int i=n;i>=1;i--) {
        for(int j=1;j<=m;j++) {
            if(a[i][j]==a[i+1][j]) f[i][j]=f[i+1][j]+1;
            else f[i][j]=1;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++) {
        int k=0;
        for(int j=1;j<=m;j++) {
            int d=f[i][j];
            if(i+d+d+d-1<=n && f[i+d][j]==d && f[i+d+d][j]>=d && a[i][j]!=a[i+d][j] && a[i+d][j]!=a[i+d+d][j]) {
                if(f[i][j-1]==d && f[i+d][j-1]==d && f[i+d+d][j-1]>=d && a[i][j]==a[i][j-1] &&
                   a[i+d][j]==a[i+d][j-1] && a[i+d+d][j]==a[i+d+d][j-1]) {
                    k++;
                }
                else {
                    k=1;
                }
            }
            else {
                k=0;
            }
            ans+=k;
        }
    }
    cout<<ans;
}

[CF1181C] Flag - dp

原文：https://www.cnblogs.com/mollnn/p/12860088.html