Golden Week Contest 2015 A 得点

2015/05/05 (Tue) AtCoder DP

問題

問題文

方針

$dp[i] = $ $i$ 点とれる or とれない とおいて埋めていく。

実装

bool ok[10000];
 
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    vi p1 = {
        25,39,51,76,163,111,/*136,*/128,133,138
    };
    vi p2 = {58,136};
    // vi p1 = {100,120};
    // vi p2 = {20,90};
    int n = p1.size();
 
    rep(i,10000) ok[i] = false;
    ok[0] = 1;
    rep(i,n){
        int p=p1[i];
        for(int i=10000;i>=0;i--){
            if(i-p >= 0) ok[i] |= ok[i-p];
        }
    }
    for(int i=10000;i>=0;i--){
        if(i-p2[0] >= 0) ok[i] |= ok[i-p2[0]];
        if(i-p2[1] >= 0) ok[i] |= ok[i-p2[1]];
    }
    rep(i,10000){
        if(ok[i]) cout << i << endl;
    }
}