UVa1172

UVa1172

DPかメモ化する。
memo[片方の岸の街][他方の岸の街]

たぶん同じ名前を持つ街が存在する。
街の名前を map のキーにするようなことは避けたほうがいい。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <sstream>

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

#define VAR(a) cout << #a << " : " << a << endl;

typedef long long int lli;

using namespace std;

const int N = 1000 + 1;

string os1[N], os2[N];
int cost1[N], cost2[N];

const pair<int, int> nil = make_pair(-1, -1);
pair<int, int> memo[N][N];

pair<int, int> better(pair<int, int> a, pair<int, int> b)
{
  if (a.first != b.first) return a.first > b.first ? a : b;
  return a.second < b.second ? a : b;
}

int size1, size2;
pair<int, int> rec(int i, int j)
{
  pair<int, int> &ret = memo[i][j];
  if (ret != nil) return ret;
  if (i == size1 || j == size2) return ret = make_pair(0, 0);

  pair<int, int> mx = make_pair(0, 0);
  mx = better(mx, rec(i + 1, j));
  mx = better(mx, rec(i, j + 1));

  if (os1[i] == os2[j]) {
    pair<int, int> p = rec(i + 1, j + 1);
    p.first += cost1[i] + cost2[j];
    ++p.second;
    mx = better(mx, p);
  }
 
  return ret = mx;
}

int main(int argc, char *argv[])
{
  int tc;
  cin >> tc;
  while (tc--) {

    cin >> size1;
    for (int i = 0; i < (int)size1; ++i) {
      string s;
      cin >> s >> os1[i] >> cost1[i];
    }

    cin >> size2;
    for (int i = 0; i < (int)size2; ++i) {
      string s;
      cin >> s >> os2[i] >> cost2[i];
    }

    fill(&memo[0][0], &memo[N - 1][N], nil);
    pair<int, int> res = rec(0, 0);
    cout << res.first << ' ' << res.second << endl;
  }
  return 0;
}