Indecision [ACPC2017 Day3 D]

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day3&pid=D

解法

http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2539793&cid=ACPC2017Day3

dp[i][cost][A] := i番目のイベントまででcostだけ使って一方のヒロインの好感度がAであるときのもう一方のヒロインの好感度Bの最大値
これを愚直にやっていくだけ。
iの部分は使いまわすとメモリ節約になる。

int N, C;
int dp[2][201][20101];
//--------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> C;
    rep(i, 0, 2) rep(j, 0, C + 1) rep(k, 0, 10101) dp[i][j][k] = -1;
    dp[0][0][0] = 0;
     
    rep(_i, 0, N) {
        int a, b, c; cin >> a >> b >> c;
 
        int i = _i % 2;
        int ii = (_i + 1) % 2;
        rep(j, 0, C + 1) rep(k, 0, 10101) dp[ii][j][k] = -1;
 
        rep(j, 0, C + 1) rep(k, 0, 10101) if(0 <= dp[i][j][k]) {
            dp[ii][j][k] = max(dp[ii][j][k], dp[i][j][k]);
            dp[ii][j + c][k + a] = max(dp[ii][j + c][k + a], dp[i][j][k] + b);
            dp[ii][j + c][k + b] = max(dp[ii][j + c][k + b], dp[i][j][k] + a);
        }
    }
 
    int ans = 0;
    rep(j, 0, C + 1) rep(k, 0, 10101) ans = max(ans, min(k, dp[N % 2][j][k]));
    cout << ans << endl;
}