GCJ 2015 Round 1C C. Less Money, More Problems

2015/05/13 (Wed) GCJ DP

問題

問題文

国には値段が相異なる $D$ 種類の貨幣があり，同じ貨幣は $C$ 枚まで使うことができる． これらを使って $V$ 円までの値段を過不足なく払えるようにしたい． そのために新たに発行する必要がある貨幣の種類数は最小でいくつか？

方針

Small は $C = 1$ である． この場合はまず既存の貨幣である値段が払えるかというのはDPで求まる (TDPC A)． 次に DP 表を小さい方から舐めて，払えないような値段が存在したらその値段の貨幣を発行し，DP 表を更新する． これを DP 表全体が true になるまで続ける．

Large はどうやるんだろう… タイムラインで log が入るオーダーが見えたので2進数表記してうまくやるのだろうか…

実装

ll solve(int C, vector<int> X, int V){
    dump(X);
    int D = X.size();
    vector<int> ok(V+1);
    ok[0] = true;
    rep(i,X.size()){
        for(int j=V;j>=0;j--){
            if(j-X[i] >= 0 && ok[j-X[i]]){
                ok[j] = true;
            }
        }
    }
    vi add;
    loop(i,1,V+1){
        if(ok[i]) continue;
        add.pb(i);
        for(int j=V;j>=0;j--){
            if(j-i >= 0 && ok[j-i]){
                ok[j] = true;
            }
        }
    }
    dump(add);
    return add.size();
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    signed T;
    cin >> T;
    rep(i,T){
        int C,D,V;
        cin >> C >> D >> V;
        vector<int> X(D);
        rep(i,D) cin >> X[i];
        ll ans = solve(C,X,V);
        printf("Case #%d: %lld\n",(int)i+1,ans);
    }
}