题目大意:有两个字符串A,B,一次刷可以把A串一段刷成同一个字母,问至少要刷几次才能把A串变成B串。串长≤100。
本来以为是个很简单的区间DP,后来发现直接区间DP是不行的,这玩意有后效性:刷完一整块之后这一块就变了。
对于这种问题不如干脆利落一点,直接把 f[ ][ ]设成将空串(即不需要考虑A与B的相同)刷成B串的最小次数。
这个时候的转移方程就是:
for(int i=;i<=n;++i)f[i][i]=;
for(int len=;len<n;++len)
for(int i=;i+len<=n;++i){
int j=i+len;f[i][j]=f[i+][j]+;
for(int k=i+;k<=j;++k)
if(B[i]==B[k])
f[i][j]=min(f[i][j],f[i+][k]+f[k+][j]);
}这个转移方程是很巧妙的。
首先赋值最坏情况,作为最大值,然后枚举k,进行更新。
转移方程的思想是:如果在B串中,i和k是一样的,就可以划分区间进行更新。
结论:在涂色的时候,区间的一个端点,一定可以作为第一个涂色。
证明:区间涂色有两种方法:分成左右 / 先整个涂一遍再在里面涂。
分成左右是子问题,先整个涂的话就可以先选择这个端点涂。
所以在转移时,如果i和k是一样的,则可以有f[i][k]=f[i+1][k],只需要在涂k的时候把整个区间涂上就可以了。
同样可以用上面的子问题思考方式证明。
这样就把"空串变B串"解决了。但是我们是要把A串变B串,答案还需要统计一遍。
设g[i]表示A串从1到i全部被涂成B的最小步数,用f来更新g。
这个时候转移方程就是这样:
g[]=A[]==B[]?:;
for(int i=;i<=n;++i){
if(A[i]==B[i]){g[i]=g[i-];continue;}
g[i]=f[][i];
for(int j=;j<i;++j)
g[i]=min(g[i],g[j]+f[j+][i]);
}这个转移也是比较有意思的,这里就不做分析了。
对于这种显然只能用DP来做的、一般的转移又有后效性的题,不妨状态设大气一点,直接忽略后效性带来的影响,再变换方式统计答案。