程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 11081 Strings(DP)

UVA 11081 Strings(DP)

編輯:C++入門知識

UVA 11081 Strings(DP)


Given 3 strings of only lowercase letter you have to count the number of ways you can construct the third string by combining two subsequences from the first two strings.

After deleting 0 or more characters from a string we can get its subsequence. For example “a”, “b”, “c”, “ab”, “ac”, “bc” and “abc” all the strings are the subsequences of “abc”. A subsequence may also be empty.

Now suppose there are two subsequences “abc” and “de”. By combining them you can get the following strings “abcde”, “abdce”, “abdec”, “adbce”, “adbec”, “adebc”, “dabce”, “dabec”, “daebc” and “deabc”.

Input

The first line of the input contains a single integer T (0

Output

For each test case output a single integer denoting the number of ways you can construct the third string from the first two string by the above way. The result may be very large. You should output the result%10007.

Sample Input Output for Sample Input

2

abc abc abc

abbcd bccde abcde

 

8

18



Problemsetter: Abdullah-al-Mahmud

Special Thanks: Md. Kamruzzaman


s1串,s2串得到s3串的方法:

#include
#include
#include
#include
#include
typedef long long LL;
using namespace std;
const int MOD=10007;
int f[70][70][70],f1[70][70][70],f2[70][70][70];
char s1[70],s2[70],s3[70];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>s1+1>>s2+1>>s3+1;
        memset(f,0,sizeof(f));
        memset(f1,0,sizeof(f1));
        memset(f2,0,sizeof(f2));
        int len1=strlen(s1+1);
        int len2=strlen(s2+1);
        int len3=strlen(s3+1);
        for(int i=0;i<=len1;i++)
        {
            for(int j=0;j<=len2;j++)
                f[i][j][0]=f1[i][j][0]=f2[i][j][0]=1;
        }
        for(int k=1;k<=len3;k++)
        {
            for(int i=0;i<=len1;i++)
            {

                for(int j=0;j<=len2;j++)
                {
                    if(i)
                    {
                        f1[i][j][k]=f1[i-1][j][k];
                        if(s1[i]==s3[k])
                            f1[i][j][k]+=f[i-1][j][k-1];
                    }
                    if(j)
                    {
                        f2[i][j][k]=f2[i][j-1][k];
                        if(s2[j]==s3[k])
                            f2[i][j][k]+=f[i][j-1][k-1];
                    }
                    f[i][j][k]=(f1[i][j][k]+f2[i][j][k])%MOD;
                }
            }
        }
        cout<

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved