yukicoder No.286 Modulo Discount Store

問題

問題概要

省略

解法

bitDP。どの商品をすでに購入したかを示す集合を要素として持ち、dpをすればいい。集合が決まっている時の、支払う金額の最小値を求めておけば、その集合内でどの順番で商品を買ったかは関係ないので、dpで解ける。
dp[mask] := (mask集合のときのしはらう金額の最小値)とすると、漸化式はdp[mask] = min(dp[mask ^ (1 << i)] + now, dp[mask])となり、maskの集合から1つ商品を取り除いた集合の支払う金額に新しく購入する商品において支払わなければならない金額を足した合計の中で、最小のものを入れればいい。

ミス

mod1000を忘れていた。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std; 
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int n;
int money[(1 << 15)];//集合の時の合計金額を計算しておく
long long dp[(1 << 15)]; //dp[mask] := mask集合のときのしはらう金額の最小値を入れておく

bool contain(int mask, int position){
    if((mask & (1 << position)) != 0) return true;
    else return false;
}
 
int main(void){
    cin >> n;
    vector<int> v(n);
    rep(i, n) cin >> v[i];

    //金額のsum
    for(int mask = 0; mask < (1 << n); ++mask){
        money[mask] = 0;//初期化
        for (int j = 0; j < n; ++j){
            //jビット目が立っているとき
            if(contain(mask, j)) money[mask] += (v[j] % 1000);
            money[mask] %= 1000;
        }
    }
    // for (int mask = 0; mask < (1 << n); ++mask) cout << money[mask] << endl;
 
    dp[0] = 0;
    for (int mask = 1; mask < (1 << n); ++mask) dp[mask] = INF;
    for (int mask = 1; mask < (1 << n); ++mask){
        rep(i, n){
            //maskのibit目を0にしたものの金額の合計を引く
            int now = v[i] - money[mask ^ (1 << i)];
            if(now < 0) now = 0;
            dp[mask] = min(dp[mask ^ (1 << i)] + now, dp[mask]);
        }
    }
    cout << dp[(1 << n) - 1] << endl;
    return 0;
}