読者です 読者をやめる 読者になる 読者になる

POJ 2184 Cow Exhibition

2184 -- Cow Exhibition
蟻本練習問題シリーズ。
dp[i][j] := iまでで、s[i]の合計がjになるときのf[i]の合計の最大
とします。
添字が負になるのでそのへんはてきとうに。
構造体にして[]演算子オーバーロードするのが楽な気がしますが、ポインタを返すのもなんとなく書いてみました。

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)
typedef long long int i64;
typedef pair<int, int> pint;

struct DP {
    static const int base = 100000;
    int data[200001];
    DP() { fill_n(data, 200001, -INF);}
    int* at(int i) { return data + base + i;}
    int& operator[] (int i) {
        assert(i + base < 200001 && i + base >= 0);
        return data[base + i];
    }
};
DP dp[2];
int S[101], F[101];
int main() {
    int N; scanf("%d", &N);
    rep(i, N) scanf("%d%d", S + i, F + i);
    int cur = 0, nxt = 1, l = 0, r = 0;
    /*
    rep(i, N) {
        *dp[nxt].at(S[i]) = max(*dp[nxt].at(S[i]), F[i]);
        REP(j, l, r + 1)
          *dp[nxt].at(j + S[i]) = max(*dp[nxt].at(j + S[i]), *dp[cur].at(j) + F[i]);
        l = min(l, l + S[i]); r = max(r, r + S[i]);
        dp[cur] = dp[nxt];
    }
    int ans = 0;
    rep(i, r + 1)
      if(*dp[cur].at(i) >= 0)
        ans = max(ans, *dp[cur].at(i) + i);
      */
    rep(i, N) {
        dp[nxt][S[i]] = max(dp[nxt][S[i]], F[i]);
        REP(j, l, r + 1)
          dp[nxt][j + S[i]] = max(dp[nxt][j + S[i]], dp[cur][j] + F[i]);
        l = min(l, l + S[i]); r = max(r, r + S[i]);
        dp[cur] = dp[nxt];
    }
    int ans = 0;
    rep(i, r + 1)
      if(dp[cur][i] >= 0)
        ans = max(ans, dp[cur][i] + i);
    printf("%d\n", ans);
//    REP(i, l, r + 1) cout << i << ' ' << *dp[cur].at(i) << endl;
    return 0;
}