結果
問題 | No.286 Modulo Discount Store |
ユーザー |
|
提出日時 | 2018-09-25 12:33:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 78 ms / 2,000 ms |
コード長 | 1,004 bytes |
コンパイル時間 | 621 ms |
コンパイル使用メモリ | 66,044 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-04 03:27:11 |
合計ジャッジ時間 | 2,192 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include<iostream> #include<climits> using namespace std; const int INF = 1<<29; int main(){ int n; cin >> n; int m[n]; for(int i = 0; i < n; i++) cin >> m[i]; int dp[n][1<<n]; for(int i = 0; i < n; i++){ for(int j = 0; j < 1<<n; j++){ dp[i][j] = INF; } } for(int i = 0; i < n; i++){ dp[i][1<<i] = m[i]; } for(int bit = 0; bit < 1<<n; bit++){ for(int i = 0; i < n; i++){ if(~bit & (1<<i)) continue; for(int j = 0; j < n; j++){ if(i == j || bit & (1<<j)) continue; int nextbit = bit | (1<<j); int teika = 0; for(int k = 0; k < n; k++) if(1<<k & bit) teika += m[k]; dp[j][nextbit] = min(dp[j][nextbit], dp[i][bit] + max(0, m[j]-(teika%1000))); } } } int ans = INT_MAX; for(int i = 0; i < n; i++) ans = min(ans, dp[i][(1<<n)-1]); cout << ans << endl; return 0; }