【Link】:
【Description】
给你两个串s1,s2;
让你生成一个串S;
使得s1和s2都是S的子列;
要求S最短;
求S的不同方案个数;
【Solution】
设两个串的长度分别为n1和n2;
则答案为n1+n2-两个串的最长公共子序列
不同的串则可以在求最长公共子序列的时候顺便求出;
设dp2[i][j],表示第一个字符串前i个字符,第二个字符串前j个字符能组成的不同的字符串的个数;
dp1[i][j]是最长公共子序列数组
如果
s1[i]==s2[j],dp2[i][j] = dp2[i-1][j-1];
(表示在dp2[i-1][j-1]所表示的所有字符串的末尾再加上一个s1[i])
s1[i]!=s2[j]:
①dp1[i-1][j]>dp1[i][j-1],则dp2[i][j] = dp2[i-1][j]
(表示在dp[i-1][j]所表示的所有字符串末尾再加上一个s1[i]);
②dp1[i-1][j]< dp1[i][j-1],则dp2[i][j] = dp2[i][j-1];
(同理)
③dp1[i-1][j]==dp1[i][j-1],则dp2[i][j] = dp2[i][j-1]+dp2[i-1][j];
(两个都是最长的,则两个都能加上s1[i]或s2[j]组成符合要求的字符串)
有空串,用gets..
【NumberOf WA】
1
【Reviw】
最长公共子序列的变形题;
【Code】
#include <bits/stdc++.h>
using namespace std;
#define LL long longconst int N = 30;char s1[N+5],s2[N+5];
LL dp1[N+5][N+5],dp2[N+5][N+5];
int n1,n2;int main(){//freopen("F:\\rush.txt","r",stdin);int T;scanf("%d",&T);getchar();for (int ii = 1;ii <= T;ii++){gets(s1+1);gets(s2+1);memset(dp1,0,sizeof dp1),memset(dp2,0,sizeof dp2);n1 = strlen(s1+1),n2 = strlen(s2+1);for (int i = 0;i <= n1;i++)dp2[i][0] = 1;for (int i = 1;i <= n2;i++)dp2[0][i] = 1;for (int i = 1;i <= n1;i++)for (int j = 1;j <= n2;j++)if (s1[i]==s2[j]){dp1[i][j] = dp1[i-1][j-1]+1;dp2[i][j] = dp2[i-1][j-1];}else{dp1[i][j] = max(dp1[i-1][j],dp1[i][j-1]);if (dp1[i-1][j] > dp1[i][j-1])dp2[i][j] = dp2[i-1][j];elseif (dp1[i-1][j] < dp1[i][j-1])dp2[i][j] = dp2[i][j-1];elsedp2[i][j] = dp2[i-1][j] + dp2[i][j-1];}printf("Case #%d: %lld %lld\n",ii,(LL) n1+n2-dp1[n1][n2],dp2[n1][n2]);}return 0;
}
