题目内容
大意:给出一块木板,要求涂色,后覆盖前,求最小笔刷数
解题思路
区间 dp。
不难发现,定义状态 f_{i,j} 为 [i,j] 的最少次数可以满足最优子结构和无后效性,具体就是要看如何转移。
枚举端点 i,j,发现如果有 s_i=s_j 的话,相当于第一次涂色的时候多涂一格,转移方程为 f_{i,j}=\min(f_{i,j-1},f_{i+1,j})
但如果 s_i\neq s_j 的话,说明没办法直接多涂一格,需要枚举中间的断点 k,由于枚举 k 的过程中必然能找到一种划分方式使得总的涂色次数加起来最优,因此只需要将断点左右加起来取最小值就可以得到该区间的答案,故有如下方程:
f_{i,j}=\min_{k\in[i,j)} \lbrace f_{i,k}+f_{k+1,j}\rbrace
#include <cstdio>
#include <cstring>
int f[55][55];
inline int min(int a,int b)
{
return a<b?a:b;
}
int main()
{
int n;
char s[55];
scanf("%s",s+1);
n=strlen(s+1);
memset(f,0x3f,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=l+1;j<=n;i++,j++)
if(s[i]==s[j])
f[i][j]=min(f[i][j-1],f[i+1][j]);
else
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
printf("%d\n",f[1][n]);
return 0;
}
留言