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; }