P4170 [CQOI2007]涂色
Loner_Knowledge
2018-02-09 12:12:32
---
题意是求对字符串的最少染色次数，设`f[i][j]`为字符串的子串`s[i]~s[j]`的最少染色次数，我们分析一下：
当`i==j`时，子串明显只需要涂色一次，于是`f[i][j]=1`。
当`i!=j`且`s[i]==s[j]`时，可以想到只需要在首次涂色时多涂一格即可，于是`f[i][j]=min(f[i][j-1],f[i+1][j])`
当`i!=j`且`s[i]!=s[j]`时，我们需要考虑将子串断成两部分来涂色，于是需要枚举子串的断点，设断点为`k`，那么`f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])`
总结一下就是：
$$f_{i,j}=1\ (i==j)$$
$$f_{i,j}=\min(f_{i,j-1},f_{i+1,j})\ (i!=j,\ s_i==s_j)$$
$$f_{i,j}=\min(f_{i,j},f_{i,k}+f_{k+1,j})\ (i!=j,\ s_i!=s_j,\ i\le k<j)$$
由于`f[i][j]`的定义，我们可以知道`f[1][n]`即为答案。
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[52];
int f[52][52];
int main() {
int n;
scanf("%s",s+1);
n=strlen(s+1);
memset(f,0x7F,sizeof(f)); //由于求最小，于是应初始化为大数
for(int i=1;i<=n;++i)
f[i][i]=1;
for(int l=1;l<n;++l)
for(int i=1,j=1+l;j<=n;++i,++j) {
if(s[i]==s[j])
f[i][j]=min(f[i+1][j],f[i][j-1]);
else
for(int k=i;k<j;++k)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
}
printf("%d",f[1][n]);
return 0;
}
```
---