您的位置:首页 > 博客中心 > 互联网 >

字符串涂漆

时间:2022-05-11 07:03

昨晚想了一晚上,最后还是看题解了/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
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

真的好难想啊qwq

本类排行

今日推荐

热门手游