C Large - Google Kickstart 2017 Round C

C.cpp

#include <bits/stdc++.h>

using namespace std;

int dp[55][55][55];
string f1, f2, me;
int n, q;

int solve(int i, int p1, int p2)
{
    if (p1 < 0 || p2 < 0) return -1000;
    if (i == q) return !p1 && !p2 ? 0 : -1000;

    int &ans = dp[i][p1][p2];
    if (ans != -1) return ans;

    ans = -1000;

    if (f1[i] == f2[i]) {
        if (me[i] == f1[i]) {
            ans = max(ans, 1 + solve(i + 1, p1 - 1, p2 - 1));
            ans = max(ans, solve(i + 1, p1, p2));
        } else {
            ans = max(ans, solve(i + 1, p1 - 1, p2 - 1));
            ans = max(ans, 1 + solve(i + 1, p1, p2));
        }
    } else {
        if (me[i] == f1[i]) {
            ans = max(ans, 1 + solve(i + 1, p1 - 1, p2));
            ans = max(ans, solve(i + 1, p1, p2 - 1));
        } else {
            ans = max(ans, 1 + solve(i + 1, p1, p2 - 1));
            ans = max(ans, solve(i + 1, p1 - 1, p2));
        }
    }

    return ans;
}

int main()
{
    int t;
    cin >> t;
    int tc = 1;

    while (t--) {
        cin >> n >> q;
        int ans = 0;

        if (n == 1) {
            int s;
            cin >> f1 >> me >> s;

            int eq = 0;
            for (int i = 0; i < q; i++) {
                if (me[i] == f1[i]) eq++;
            }
            ans = q - abs(s - eq);
        } else {
            int s1, s2;
            cin >> f1 >> f2 >> me >> s1 >> s2;
            memset(dp, -1, sizeof dp);
            ans = solve(0, s1, s2);
        }

        cout << "Case #" << tc++ << ": " << max(ans, 0) << endl;
    }

    return 0;
}