字符串涂漆

技术文章 10个月前 完美者
1,308 0

标签:否则   href   字符   space   target   main   can   mes   namespace   

昨晚想了一晚上,最后还是看题解了/kk

约用时 20min。

因为要考虑到原来的字符串有的字母是可以保留的,所以在按上一题的方法求过一遍之后,还需要再次决策。

设 g[i] 表示从 1 ~ i 所需的最少次数,则分为两种情况:

  • a[i] == b[i] 时,也就是说第 i 个位置就不用涂了,保留原来的颜色即可,所以 g[i]=g[i-1]

  • 否则枚举分界点,而对于分界点 j ,它的代价就是 1 ~ j(不含 j ) 的最小次数加上 j ~ i(含 i,j ) 的最小次数,也就是 g[i]=g[j-1]+f[j][i]

感觉和分段 dp 有点像。

话说我又忘赋初值了/xk

#include<bits/stdc++.h>
using namespace std;
char a[201],b[201];
int n;
int f[201][201],g[201];
int main()
{
    scanf("%s%s",a+1,b+1);
    n=strlen(a+1);
    for(int i=1;i<=n;i++)//上道题的做法
    {
    	g[i]=2e9;
        for(int j=1;j<=n;j++) f[i][j]=2e9;
    }
    for(int i=1;i<=n;i++) f[i][i]=1;
    for(int l=2;l<=n;l++)
    {
        for(int i=1;i<=n-l+1;i++)
        {
            int j=i+l-1;
            for(int k=i;k<j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            if(b[i]==b[j]) f[i][j]--;
        }
    }
    for(int i=1;i<=n;i++)//再次决策
    {
    	if(b[i]==a[i]) g[i]=g[i-1];
    	else
    	{
    		g[i]=f[1][i];
    		for(int j=2;j<=i;j++) g[i]=min(g[i],g[j-1]+f[j][i]);
    	}
    }
    cout<<g[n]<<endl;
    return 0;
}

真的好难想啊qwq

字符串涂漆

标签:否则   href   字符   space   target   main   can   mes   namespace   

原文地址:https://www.cnblogs.com/ying-xue/p/zi-fu-chuan-tu-qi.html

版权声明:完美者 发表于 2020-12-18 12:19:06。
转载请注明:字符串涂漆 | 完美导航

暂无评论

暂无评论...