(UVA) 1172 - The Bridges of Kolsberg

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=3613

Tips : LCS + DP

#include <iostream>
#include <stdio.h>
#include <map>
#include <cstring>
#include <utility>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 1006;

pii dp[MAX_N][MAX_N];
map<string,int> mp;
int a[MAX_N],b[MAX_N],c[MAX_N],d[MAX_N];

pii operator+(const pii &p1,const pii &p2) {
    return make_pair(p1.first+p2.first,p1.second+p2.second);
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n;
        scanf("%d",&n);
        mp.clear();
        int id=1;
        for (int x=1;n>=x;x++) {
            string s,t;
            int v;
            cin >>s >>t >> v;
            int ret=mp[t];
            if (!ret) {
                ret = mp[t] = id++;
            }
            a[x] = ret;
            b[x] = v;
        }
        int m;
        scanf("%d",&m);
        for (int x=1;m>=x;x++) {
            string s,t;
            int v;
            cin >>s >>t >> v;
            int ret=mp[t];
            if (!ret) {
                ret = mp[t] = id++;
            }
            c[x] = ret;
            d[x] = v;
        }
        for (int i=0;n>=i;i++) {
            for (int j=0;m>=j;j++) {
                dp[i][j] = make_pair(0,0);
            }
        }
        for (int i=1;n>=i;i++) {
            for (int j=1;m>=j;j++) {
                pii mx = max(dp[i-1][j],dp[i][j-1]);
                pii ret = make_pair(0,0);
                if (a[i] == c[j]) {
                    ret = make_pair(b[i]+d[j],-1) + dp[i-1][j-1];
                }
                dp[i][j] = max(mx,ret);
            }
        }
        printf("%d %d\n",dp[n][m].first,-dp[n][m].second);
    }
}