典型的代价优先计算dp
难点就在计算代价上。。。
很巧的是，每次合并，代价就是i,j组成的序列中，开始了但是没有结束的字母种类数
【1】普通dp tle不知道多少个点
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> using namespace std; inline int read() { int x=0;char c=getchar(); while(c<'0' || c>'9' ) c=getchar(); while(c>='0'&&c<='9' ) x=(x<<3)+(x<<1)+c-'0',c=getchar(); return x; } inline void wr(int x) { if(x>=10) wr(x/10); putchar(x%10+'0'); } int n; const int N=5e3+3; char a[N],b[N]; int la,lb,da[N],db[N]; int sum[26],cnt[2][N][26]; int w[N][N]; int f[N][N]; int main() { int T; scanf("%d",&T); while(T--) { memset(cnt,0,sizeof(cnt)); memset(sum,0,sizeof(sum)); la=lb=0; //pre0 scanf("%s%s",a+1,b+1); while(a[++la]) da[la]=a[la]-'A',sum[da[la]]++,cnt[0][la][da[la]]++; while(b[++lb]) db[lb]=b[lb]-'A',sum[db[lb]]++,cnt[1][lb][db[lb]]++; la--,lb--; for(int i=1;i<=la;i++) { int res=0; for(int j=0;j<26;j++) { cnt[0][i][j]+=cnt[0][i-1][j]; if(cnt[0][i][j] && cnt[0][i][j]!=sum[j] ) res++; } w[i][0]=res; } for(int i=1;i<=lb;i++) { int res=0; for(int j=0;j<26;j++) { cnt[1][i][j]+=cnt[1][i-1][j]; if(cnt[1][i][j] && cnt[1][i][j]!=sum[j] ) res++; } w[0][i]=res; } //pre1 for(int i=1;i<=la;i++) for(int j=1;j<=lb;j++) { w[i][j]=w[i][j-1]; if(cnt[0][i][db[j]] + cnt[1][j][db[j]] ==sum[db[j]] ) w[i][j]--; if(!cnt[1][j-1][db[j]] && !cnt[0][i][db[j]] ) w[i][j]++; } //work memset(f,0x3f,sizeof(f)); f[0][0]=0; for(int j=1;j<=lb;j++) f[0][j]=f[0][j-1]+w[0][j-1]; for(int i=1;i<=la;i++) { f[i][0]=f[i-1][0]+w[i-1][0]; for(int j=1;j<=lb;j++) f[i][j]=min(f[i][j-1]+w[i][j-1],f[i-1][j]+w[i-1][j] ), printf("%d ",f[i][j]); printf(" "); } wr(f[la][lb]),putchar(' '); } return 0; }
【2】滚动数组优化 时间和空间
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> using namespace std; inline int read() { int x=0;char c=getchar(); while(c<'0' || c>'9' ) c=getchar(); while(c>='0'&&c<='9' ) x=(x<<3)+(x<<1)+c-'0',c=getchar(); return x; } inline void wr(int x) { if(x>=10) wr(x/10); putchar(x%10+'0'); } int n; const int N=5e3+3; char a[N],b[N]; int la,lb,da[N],db[N]; int sum[26],cnt[2][N][26]; int w[2][N]; int f[2][N]; int main() { int T; scanf("%d",&T); while(T--) { memset(cnt,0,sizeof(cnt)); memset(sum,0,sizeof(sum)); memset(f,0x3f,sizeof(f)); la=lb=0; //pre0 scanf("%s%s",a+1,b+1); while(a[++la]) da[la]=a[la]-'A',sum[da[la]]++,cnt[0][la][da[la]]++; while(b[++lb]) db[lb]=b[lb]-'A',sum[db[lb]]++,cnt[1][lb][db[lb]]++; la--,lb--; for(int i=1;i<=la;i++) for(int j=0;j<26;j++) cnt[0][i][j]+=cnt[0][i-1][j]; for(int i=1;i<=lb;i++) for(int j=0;j<26;j++) cnt[1][i][j]+=cnt[1][i-1][j]; f[0][0]=w[0][0]=0; for(int i=1;i<=lb;i++) { w[0][i]=w[0][i-1]; if(!cnt[1][i-1][db[i]] ) w[0][i]++; if( cnt[1][i][db[i]] == sum[db[i]] ) w[0][i]--; f[0][i]=f[0][i-1]+w[0][i-1]; } for(int i=1;i<=la;i++) { int nw=i&1,pre=nw^1; //pre1 w[nw][0]=w[pre][0];//对应w[i][0] if(cnt[0][i][da[i]] == sum[da[i]]) w[nw][0]--; if(cnt[0][i-1][da[i]] == 0 ) w[nw][0]++; for(int j=1;j<=lb;j++)//对应w[i][j] { w[nw][j]=w[nw][j-1]; if(cnt[0][i][db[j]] + cnt[1][j][db[j]] ==sum[db[j]] ) w[nw][j]--; if(!cnt[1][j-1][db[j]] && !cnt[0][i][db[j]] ) w[nw][j]++; } //work f[nw][0]=f[pre][0]+w[pre][0]; for(int j=1;j<=lb;j++) f[nw][j]=min(f[pre][j]+w[pre][j],f[nw][j-1]+w[nw][j-1]); } wr(f[la&1][lb]),putchar(' '); } return 0; }