[yukicoder] No. 286 Modulo Discount Store

2019年6月28日2019年9月30日

問題

方針

\( k \) 個商品を購入したとき、\( k + 1 \) 個目の商品を購入するときの割引は、\( k \) 個商品を購入したときの順番に依存しません。この考えをもとにして、bitDP を行います。

bitDP

\( i \) をビット列として、フラグが立っているときその商品を購入していることを表すとします。例えば、\( 0101 \) は、\( 1 \) と \( 3 \) 番目の商品を購入していることを表します。また、ビット列は文字列ではなく整数として扱い、購入した商品の集合であることを表します。

ここで、\( j  \ (0 \leq j < N ) \) を商品番号とします。ある集合 \( i \) に対して、\( i \ \& \  (2^{j} – 1) \neq 1 \) のとき、その商品は購入されています。配列 \( d \) の要素 \( d_i \) を、購入した商品の集合 \( i \) に対する最小の購入金額とします。集合 \( i \) に対して、商品の合計金額 \( v \) を求め、配列の更新を行います。\( i \ \& \  (2^{j} – 1) = 0 \) となる \( i, j\) について、配列の添え字を \( k = i \ | \ (2^{j} – 1) \) とします。\( k \) は、集合 \( i \) に商品 \( j \) を追加した集合になります。配列の更新は、

\[d_k = \min (d_k, \max (0, M_j – cost))\]

とします。\( d_{2^{N} – 1} \) が答えになります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  int M[N];
  for (int i = 0; i < N; i++) {
    cin >> M[i];
  }
  
  int dp[1<<N];
  for (int i = 0; i < (1<<N); i++) {
    dp[i] = 100000000;
  }
  dp[0] = 0;
  for (int i = 0; i < (1<<N); i++) {
    int cost = 0;
    for (int j = 0; j < N; j++) {
      // 購入済みの商品の合計金額を求める
      if ((i & (1<<j)) != 0) {
        cost += M[j];
      }
    }
    cost %= 1000;
    for (int j = 0; j < N; j++) {
      // 購入していない商品 j を購入する
      if ((i & (1<<j)) == 0) {
        int idx = i | (1<<j);
        dp[idx] = min(dp[idx], dp[i] + max(0, M[j] - cost));
      }
    }
  }
  cout << dp[(1<<N) - 1] << "\n";
  return 0;
}