程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LightOJ1013---Love Calculator (dp)

LightOJ1013---Love Calculator (dp)

編輯：C++入門知識

LightOJ1013---Love Calculator (dp)

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:

The length of the shortest string that contains the names as subsequence.

Total number of unique shortest strings which contain the names as subsequence.

Now your task is to find these parts.
Input

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.
Output

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.
Sample Input

Output for Sample Input

USA

USSR

LAILI

MAJNU

SHAHJAHAN

MOMTAJ

Case 1: 5 3

Case 2: 9 40

Case 3: 13 15

f[i][j]表示第一個串匹配到i,第二個串匹配到j需要的最短長度
dp[i][j]表示f[i][j]長度下的方案數
轉移很簡單
但是有一個地方要注意:
如果A[i]==B[j],那麼方案數計算的時候,只能從f[i?1][j?1]處轉移到, 如果從f[i?1][j]f[i][j?1]轉移,會重復

/*************************************************************************
    > File Name: LightOJ1013.cpp
    > Author: ALex
    > Mail: [email protected] 
    > Created Time: 2015年06月07日 星期日 21時41分25秒
 ************************************************************************/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 

using namespace std;

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair  PLL;

string A, B;
LL dp[50][50];
int f[50][50];

int main() {
    int t, icase = 1;
    scanf("%d", &t);
    while (t--) {
        cin >> A >> B;
        int n = A.length();
        int m = B.length();
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        memset(f, inf, sizeof(f));
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            f[i][0] = i;
            dp[i][0] = 1;
        }
        for (int j = 1; j <= m; ++j) {
            f[0][j] = j;
            dp[0][j] = 1;
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (f[i][j] > f[i - 1][j] + 1) {
                    f[i][j] = f[i - 1][j] + 1;
                }
                if (f[i][j] > f[i][j - 1] + 1) {
                    f[i][j] = f[i][j - 1] + 1;
                }
                if (A[i - 1] == B[j - 1]) {
                    if (f[i][j] > f[i - 1][j - 1] + 1) {
                        f[i][j] = f[i - 1][j - 1] + 1;
                    }
                }
                if (f[i][j] == f[i - 1][j] + 1 && A[i - 1] != B[j - 1]) {
                    dp[i][j] += dp[i - 1][j];
                }
                if (f[i][j] == f[i][j - 1] + 1 && A[i - 1] != B[j - 1]) {
                    dp[i][j] += dp[i][j - 1];
                }
                if (A[i - 1] == B[j - 1] && f[i][j] == f[i - 1][j - 1] + 1) {
                    dp[i][j] += dp[i - 1][j - 1];
                }

            }
        }
        printf("Case %d: %d %lld\n", icase++, f[n][m], dp[n][m]);
    }
}