POJ2184: Cow Exhibtion

概要

100個以下の要素からなる(S[i],F[i])の列がある．(-1000<=S[i],F[i]<=1000)
この列からいくつかの要素を選び，S[i]，F[i]の総和をとる．
S[i]の総和とF[i]の総和が0を下回らないという条件のもとで，S[i]とF[i]の総和を最大にする．

解法

S[i]について降順にソート．
dp[i][j]:=(i番目までの要素を用いてS[i]の総和をjとするときのF[i]の総和の最大値．不可能なら負の無限大)
としてDP．

struct Cow{
    int s, f;
    Cow(int s, int f) : s(s),f(f) {}
    Cow() {}
};
bool operator<(const Cow &a, const Cow &b){
    if(a.s != b.s) return a.s < b.s;
    else return a.f < b.f;
}
int N;
Cow c[110];
int dp[2][100010];

const int INF = 100000000;
int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; ++i){
        scanf("%d%d", &(c[i].s), &(c[i].f));
    }
    sort(c, c+N);
    reverse(c, c+N);
    dp[0][0] = 0;
    for(int i = 1; i < 100010; ++i) dp[0][i] = -INF;

    int *prev = dp[0], *next = dp[1];
    for(int i = 0; i < N; ++i){
        for(int j = 0; j <= 100000; ++j){
            next[j] = prev[j];
            if(0<=j-c[i].s && j-c[i].s<=100000 && prev[j-c[i].s] != -INF)
                next[j] = max(next[j], prev[j-c[i].s] + c[i].f);
        }
        swap(next, prev);
    }
    int res = 0;
    for(int i = 0; i <= 100000; ++i)
        if(prev[i] >= 0) res = max(res, i + prev[i]);
    printf("%d\n", res);
    return 0;
}

pairを使ったほうがよかった．