POJ-2184: Cow Exhibition

keyword

動的計画法　C

問題概要

長さN(<100)の点列(x,y) in [-R..R]^2(R=10^3)が与えられる。x+yの部分和の最大値を求めよ。ただし、xのみの部分和とyのみの部分和が共に非負でなければならない。

解法

範囲が狭いのがとても怪しい。もしGreedyで上手くいくならRはもっと大きく設定するだろう。
というわけでDPで考える。別にそういう本筋でない考え方を抜きにしても、情報をたくさん捨てても困らないときにはDPが使えることは多い。
で、この問題をDPで解くにはdp[k番目の点まで見た][xの部分和] = (yの最大の部分和)　とすれば良い。xの部分和の範囲は[-N*R..N*R]なので全部とっておける(実は下限はもう少し削れるけど、せいぜい定数倍の差)。ただしN*N*2*Rはさすがに大きいので、dpテーブルは使いまわしてメモリを省略する。時間計算量O(N^2*R)。空間計算量O(N*R)。

#define MAX_N 102
#define MAX_RANGE (100*2000+2)
#define INF (1<<29)

int dp[2][MAX_RANGE];
int N;
int S[MAX_N], F[MAX_N];

int max(int x, int y){ return x>y?x:y; }

int solve(){
    int ans=0, i, k, cur, next;
    for(i=0;i<MAX_RANGE;i++) dp[0][i] = -INF;
    dp[0][100000] = 0;
    for(k=0;k<N;k++){
        cur = k&1, next = 1-cur;
        for(i=0;i<MAX_RANGE;i++) dp[next][i] = -INF;
        for(i=0;i<MAX_RANGE;i++)if(dp[cur][i]!=-INF){
            dp[next][i] = max(dp[next][i], dp[cur][i]);
            dp[next][i+S[k]] = max(dp[next][i+S[k]], dp[cur][i]+F[k]);
        }
    }
    for(i=100000;i<MAX_RANGE;i++)if(dp[N&1][i]>=0){
        ans = max(ans, (i-100000)+dp[N&1][i]);
    }
    return ans;
}

main(){
    int i;
    scanf("%d",&N);
    for(i=0; i<N; i++)
        scanf("%d%d",S+i,F+i);
    printf("%d\n",solve());
}