题解 P4170 【[CQOI2007]涂色】
whyl
2019-09-19 14:27:40
同zzy2333神犇
本蒟蒻也在考场上写出了一个和别的题解不一样的dp
但是可以A掉模拟赛和洛谷的数据
仅供参考
也欢迎各位大佬前来hack。
```cpp
#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;
}
```