UVa

Luogu

分析

比较奇妙的 DP 题...

设 $g_{i,j}$ 表示空串刷成 $B_{i..j}$ 的最小次数,转移很简单。

然后设 $f_i$ 表示 $A_{1..i}$ 刷成 $B_{1..i}$ 的最小次数。转移也比较简单。

然后答案就是 $f_n$ 。

感觉这题的难点不在转移而在思想...

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10;

int n;
char A[N],B[N];
int f[N],g[N][N];

int main() {
    while (scanf("%s%s",A+1,B+1)==2) {
        memset(f,0x3f,sizeof(f)),memset(g,0x3f,sizeof(g));
        n=strlen(A+1);
        for (re int i=1;i<=n;++i) g[i][i]=1;
        for (re int l=2;l<=n;++l)
            for (re int i=1,j=i+l-1;j<=n;++i,++j) {
                if (B[i]==B[j]) g[i][j]=max(g[i+1][j],g[i][j-1]);
                else {
                    for (re int k=i;k<j;++k)
                        g[i][j]=min(g[i][j],g[i][k]+g[k+1][j]);
                }
            }
        f[1]=(A[1]==B[1])?0:1; //这个边界有点迷
        for (re int i=2;i<=n;++i) {
            f[i]=g[1][i];
            if (A[i]==B[i]) f[i]=min(f[i],f[i-1]);
            else {
                for (re int k=1;k<i;++k)
                    f[i]=min(f[i],f[k]+g[k+1][i]);
            }
        }
        printf("%d\n",f[n]);
    }
    return 0;
}
最后修改:2019 年 12 月 07 日 03 : 17 PM