Aizu Online Judge 2607 - Invest Master

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2607

問題文が日本語なので特になしです。

解法

解けませんでしたー
重さを所持金、コストを翌日の所持金、そして日数x株の種類の荷物があるとすれば個数制限なしのナップザック問題と考えることができます。数制限なしのナップザックが配列を再利用できることを考えると、
:=所持金がのときの翌日の所持金の最大値
と定義することができます。あとは蟻本まんまですね。

ソースコード

#include <cstdio>
#include <algorithm>
using namespace std;

int dp[100010], p[11][11];

int main() {
    int n, d, x, have;
    scanf("%d %d %d", &n, &d, &x);

    for (int i = 0; i < d; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &p[i][j]);
        }
    }

    have = x;
    for (int i = 0; i < d - 1; i++) {
        for (int j = 0; j <= have; j++) dp[j] = j;
        for (int j = 0; j < n; j++) {
            for (int k = 0; k <= have; k++) {
                if (k - p[i][j] >= 0) {
                    dp[k] = max(dp[k], dp[k - p[i][j]] + p[i + 1][j]);
                }
            }
        }
        int nhave = 0;
        for (int j = 0; j <= have; j++) nhave = max(nhave, dp[j]);
        have = nhave;
    }

    printf("%d\n", have);
 
    return 0;
}

感想

ナップザック問題だということには気づいていたのですが翌日の値についてDPするというのは全く頭に浮かびませんでした。しっかり勉強します。