RUPC2016 Day2 G : Max Pig Noodle

本番でctylさんが解法を編み出し、自分が実装した問題。

問題

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

解法

DP。int dp[xの残量][yの残量] = このx, yで実現できる最大のブタメソの最大個数とすればよい。交換人の順序はバラバラであってもよいが、これはx, yに負の値を認めると交換人を1人目から順に見ていくだけでよくなる。最後にx, yが正の領域でブタメソの最大値を取ればOK。計算量は100 * 600 * 600で間に合う。

以下のコードでは dp[y][ブタメソ] = x としている。こうするとちょっとメモリが減る。

const int CENTER = 300;
const int INF = 999;
const int MAX_H = 601;
const int MAX_W = 301;

int dp1[MAX_H][MAX_W];
int dp2[MAX_H][MAX_W];

signed main() {
    int n;
    cin >> n;
    int x, y;
    cin >> x >> y;

    vi a(n), b(n), c(n), d(n);
    rep(i, n) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }

    rep(i, MAX_H) rep(j, MAX_W) {
        dp1[i][j] = -INF;
        dp2[i][j] = -INF;
    }

    dp1[y + CENTER][0] = x;

    rep(k, n) {
        rep(i, MAX_H) {
            rep(j, MAX_W) {
                if (dp1[i][j] == -INF)
                    continue;

                dp2[i][j] = max(dp2[i][j], dp1[i][j]);
                if (i + b[k] < MAX_H) {
                    dp2[i + b[k]][j] = max(dp2[i + b[k]][j], dp1[i][j] - a[k]);
                }
                if (i - c[k] >= 0) {
                    dp2[i - c[k]][j + d[k]] = max(dp2[i - c[k]][j + d[k]], dp1[i][j]);
                }
            }
        }
        rep(i, MAX_H) rep(j, MAX_W) dp1[i][j] = dp2[i][j];
    }

    int ma = 0;
    rep2(i, CENTER, MAX_H) {
        rep(j, MAX_W) {
            if (dp2[i][j] >= 0) {
                ma = max(ma, j);
            }
        }
    }

    cout << ma << endl;

}