lightoj 1013 - Love Calculator - dblank

lightoj 1013 - Love Calculator

Yes, you are developing a 'Love calculator'. The software would be quite complex such that nobody could crack the exact behavior of the software.

So, given two names your software will generate the percentage of their 'love' according to their names. The software requires the following things:

  1. The length of the shortest string that contains the names as subsequence.
  2. Total number of unique shortest strings which contain the names as subsequence.

Now your task is to find these parts.
<h1>Input</h1>
Input starts with an integer T (≤ 125), denoting the number of test cases.

Each of the test cases consists of two lines each containing a name. The names will contain no more than 30 capital letters.
<h1>Output</h1>
For each of the test cases, you need to print one line of output. The output for each test case starts with the test case number, followed by the shortest length of the string and the number of unique strings that satisfies the given conditions.

You can assume that the number of unique strings will always be less than 263. Look at the sample output for the exact format.

<h1>Sample Input</h1> <h1>Output for Sample Input</h1>
3 USA USSR LAILI MAJNU SHAHJAHAN MOMTAJ Case 1: 5 3 Case 2: 9 40 Case 3: 13 15

题意:给你两个字符串,让你构造一个字符以最小的长度包含这俩个字符串(可以不连续),并且让你求方案数。

思路:很明显最小长度是这俩个字符串的长度和减去它们的lcs。对于方案数,我们可以定义dplen[j]表示构造到长度为len时,这len包含了s串的前i个字符和包含了x串的前j个字符。于是对于构造的第len个字符我们有两种选择,

放置s的第i个和x的第j个字符。如果s[i] == s[j]就只有一种了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 3e1 + 10, Mod = 1000000007;
typedef long long ll;
char s[N], x[N];
ll dp2*N[N];
int lcsN;
int main()
{
    int t;
    scanf("%d", &t);
    for(int cas = 1; cas<=t; cas++)
    {
        scanf("%s%s", s, x);
        memset(dp, 0, sizeof(dp));
        memset(lcs, 0, sizeof(lcs));
        int ls = strlen(s), lx = strlen(x);
        for(int i = 1; i<=ls; i++)
            for(int j = 1; j<=lx; j++)
            {
                if(s[i-1] == x[j-1])
                    lcsi = lcsi-1 + 1;
                else lcsi = max(lcsi-1, lcsi);
            }
        int len = lx + ls - lcsls;
        dp0[0] = 1;
        for(int i = 0; i<=len; i++)
        {
            for(int j = 0; j<=ls; j++)
                for(int r = 0; r<=lx; r++)
                {
                    if(s[j] == x[r])
                    {
                        dpi+1[r+1] += dpi[r];
                    }
                    else
                    {
                        dpi+1[r] += dpi[r];
                        dpi+1[r+1] += dpi[r];
                    }
                }

        }
        printf("Case %d: %d %lldn", cas,len, dplen[lx]);
    }
    return 0;
}

 

相关文章

发表新评论