LightOJ 1013 Love Calculator (LCS+DP)

谁借莪１个温暖的怀抱￠ 2022-09-18 04:57 115阅读 0赞

题目链接：http://lightoj.com/volume\_showproblem.php?problem=1013

题意：给出两个字符串，求一个字符串，使得另两个字符串为该串的子序列(也就是说不必每个字母都相邻)，求该串的最小长度，并求出在最小长度的情况下，该串可以有多少种不同的构成。

思路：LCS变形，最小长度=两串长度之和-两串的LCS的长度。接下来用DP求有多少种不同的构成。

dp\[i\]\[j\]\[k\]表示构成用第一个串的前j个字符(str\[0……j-1\])和第二个串的前k个字符(ch\[0……k-1\])构成长度为i的串的方法数。

具体状态转移见代码

#include <cstdio>
    #include <cstring>
    #define max(a,b) ((a)>(b)?(a):(b))
    
    const int N=32;
    
    int dp[2][N];  /* 存储LCS长度 */
    __int64 f[2*N][N][N];
    char str[N],ch[N];
    
    int LCS (int lenstr,int lench)
    {//返回LCS的长度
    	memset(dp,0,sizeof(dp));
    	int k;
    	for (int i=1;i<=lenstr;i++)
    	{
    		k=i&1;
    		for (int j=1;j<=lench;j++)  
    			if (str[i-1] == ch[j-1])  
    				dp[k][j]=dp[k^1][j-1]+1;  
    			else
    				dp[k][j]=max(dp[k][j-1],dp[k^1][j]);
    	}
    	return dp[k][lench];
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		scanf("%s%s",str,ch);
    		int lenstr=strlen(str);
    		int lench=strlen(ch);
    		int lenlcs=LCS(lenstr,lench);
    		int ans=lenstr+lench-lenlcs;
    		memset(f,0,sizeof(f));
    		f[0][0][0]=1;
    		
    		for (int i=0;i<=ans;i++) for (int j=0;j<=lenstr;j++)
    			for (int k=0;k<=lench;k++) if (f[i][j][k])
    				if (str[j]!=ch[k])
    				{
    					f[i+1][j+1][k]+=f[i][j][k];
    					f[i+1][j][k+1]+=f[i][j][k];
    				}
    				else
    					f[i+1][j+1][k+1]+=f[i][j][k];
    		printf("Case %d: %d %lld\n",Cas,ans,f[ans][lenstr][lench]);
    	}
    	return 0;
    }
    /*
    4
    W
    NHKEBMTD
    XJOQKDVFEPVL
    O
    HQGHUMEAYLNL
    DXFIRCVSCXGGBWKFNQDUXWFNFOZV
    ABABABABABABABABABABAB
    CDCDCDCDCDCDCDCDCDCDCD
    
    Output:
    Case 1: 9 9
    Case 2: 12 1
    Case 3: 37 208320
    Case 4: 44 2104098963720
    */