結果
問題 |
No.286 Modulo Discount Store
|
ユーザー |
![]() |
提出日時 | 2016-07-30 12:28:00 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 1,147 bytes |
コンパイル時間 | 551 ms |
コンパイル使用メモリ | 56,848 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-06 21:02:08 |
合計ジャッジ時間 | 1,848 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
//とってもとっても自信ない #include <iostream> using namespace std; int n; int m[15]; int dp[1<<15]; //rem = 残っている商品の組み合わせ, (remの下位iビット目が1 ⇔ 商品iが残っている) //返す値 = 残っている商品を購入するときの、購入金額の最小値 int dfs(int rem) { if (rem == 0) return 0; if (dp[rem] != -1) return dp[rem]; //メモを使う(既に計算しているのでそれを返す) int subCost = 0; //割引額 int i; //商品番号 int ret = 11451419; //返す値 for (i = 0; i < n; i++) if ((rem >> i) % 2 == 0) subCost += m[i]; subCost %= 1000; for (i = 0; i < n; i++) { if ((rem >> i) % 2) { //商品iを購入する(場合) int cost = max(0, m[i] - subCost) + dfs(rem - (1 << i)); ret = min(ret, cost); } } return (dp[rem] = ret); //メモをしてから返す(同じrem値で呼び出した時の再計算を防ぐため) } int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> m[i]; } for (int i = 0; i < (1 << n); i++) { dp[i] = -1; } //undefinedフラグ = -1 cout << dfs((1 << n) - 1) << endl; return 0; }