SRM 371 Div1 Medium ChessMatchUp

問題

チェスの団体戦を行う。自チームと相手チームの各人の強さが数値で与えられる。勝てば2ポイント、引き分けで1ポイント得点が入るとする。相手チームとの組み合わせを好きにできるとき、自チームの最大の得点を求めよ。

やりかた

強さでソートした上でDP。
dp[i][j] :=（i番目の選手を相手チームj番目の選手と当たらせた時の最大の得点）

以下ソース。

int dp[51][51];

class ChessMatchup {  
public:
  int N;
  vector<int> u, t;
  int rec(int idx, int jdx){
    if(idx == N || jdx == N) return 0;
    if(dp[idx][jdx] != -1) return dp[idx][jdx];

    int ans = 0;
    for(int j = jdx; j < N; j++){
      if(u[idx] > t[jdx]) ans = max(ans, 2 + rec(idx + 1, j + 1));
      if(u[idx] == t[jdx]) ans = max(ans, 1 + rec(idx + 1, j + 1));
    }
    //自チームの今の選手が相手チームのどの選手とあたっても
    //得点が入らない時はおとなしく次鋒の選手に渡す
    ans = max(ans, rec(idx + 1, jdx));

    return dp[idx][jdx] = ans;
  }
  int maximumScore(vector <int> us, vector <int> them) {
    sort(ALL(us));
    sort(ALL(them));
    N = us.size();
    u = us; t = them;

    memset(dp, -1, sizeof(dp));
    return rec(0, 0);
  }
};