题解 P4170 【[CQOI2007]涂色】

2019-09-19 14:27:40


同zzy2333神犇

本蒟蒻也在考场上写出了一个和别的题解不一样的dp

但是可以A掉模拟赛和洛谷的数据

仅供参考

也欢迎各位大佬前来hack。

#include<bits/stdc++.h>

using namespace std;

#define re register

inline int read(){
    int x=0,f=1;
    char p=getchar();
    while(!isdigit(p)){
        if(p=='-') f=-1;
        p=getchar();
    }
    while(isdigit(p)) x=(x<<3)+(x<<1)+p-48,p=getchar();
    return x*f;
} 

const int maxn=1005;

int n,f[maxn][maxn];
char a[maxn];

int main(){
//  freopen("segtree.in","r",stdin);
//  freopen("segtree.out","w",stdout);
    cin>>(a+1);
    n=strlen(a+1);
    for(re int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=1e9;
    for(re int i=1;i<=n;i++) f[i][i]=1;
    for(re int len=2;len<=n;len++){
        for(re int l=1,r=l+len-1;r<=n;l++,r++){
            for(re int k=l;k<r;k++){
                if(a[l]==a[r]) f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]-1); 
                if(a[k]==a[k+1]) f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]-1);
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
            }
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}