UVA10723 Cyborg Genes

题目传送门

Uva变了，以后恐怕不能叫它Uva了……

---

第一问还是很简单的，直接求最长公共子序列的长度，那么这两个字符串的长度 - 2 * 最长公共子序列的长度就是答案

第二问统计方案数还是有点意思的
要注意当f[i-1][j] == f[i][j-1]的时候，方案可以同时从这两边转移过来

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        k = k * 10 + c - 48; c = getchar();
    }
    return k * f;
}
LL tot = 0, f[50][50], cnt[50][50];
void solve() {
    memset(f, 0, sizeof(f)), memset(cnt, 0, sizeof(cnt));
    string s1, s2;
    getline(cin, s1); getline(cin, s2);
    int len1 = s1.size(), len2 = s2.size();
    for(int i = 0; i <= 40; ++i) cnt[i][0] = cnt[0][i] = 1; 

    for(int i = 1; i <= len1; ++i)
        for(int j = 1; j <= len2; ++j) {
            if(f[i][j-1] > f[i-1][j]) cnt[i][j] = cnt[i][j-1];
            else if(f[i][j-1] < f[i-1][j]) cnt[i][j] = cnt[i-1][j];
            else cnt[i][j] = cnt[i-1][j] + cnt[i][j-1];
            
            f[i][j] = max(f[i][j-1], f[i-1][j]);
            if(s1[i-1] == s2[j-1]) {
                f[i][j] = f[i-1][j-1] + 1;
                cnt[i][j] = cnt[i-1][j-1];
            }
        }
    printf("Case #%lld: %lld %lld
", tot, len1 + len2 - f[len1][len2], cnt[len1][len2]);
}
int main() {
    int k; scanf("%d
", &k);
    while(k--) {
        ++tot;
        solve();
    }
    return 0;
}