結果
問題 | No.324 落ちてた閉路グラフ |
ユーザー |
![]() |
提出日時 | 2015-12-15 13:00:33 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 80 ms / 5,000 ms |
コード長 | 2,762 bytes |
コンパイル時間 | 2,353 ms |
コンパイル使用メモリ | 163,128 KB |
実行使用メモリ | 74,092 KB |
最終ジャッジ日時 | 2024-11-15 19:19:25 |
合計ジャッジ時間 | 4,348 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int inf = 1e9; const int MIN_N = 3; const int MAX_N = 3000; const int MIN_M = 0; const int MAX_M = MAX_N; const int MIN_W = -300; const int MAX_W = 300; int naive(const vector<int> &w, int m){ int n = w.size(); int best = -inf; for(int S = 0; S < 1<<n; S++){ int c = __builtin_popcount(S); if(c != m) continue; int sum = 0; for(int i = 0; i < n; i++){ if((S >> i & 1) & (S >> ((i+1)%n) & 1)){ sum += w[i]; } } best = max(best, sum); } return best; } int solve(vector<int> w, int m){ int n = w.size(), ans = -inf; for(int t = 0; t < 2; t++){ // t = 0 -> 0 番目を取る, t = 1 -> とらない static int dp[MAX_N+10][MAX_M+10][2]; // [0,i) 個めで j 個とったときの最大値 for(int i = 0; i <= n; i++){ for(int j = 0; j <= m; j++){ dp[i][j][0] = dp[i][j][1] = -inf; } } dp[0][t][t] = 0; for(int i = 0; i < n; ++i) { for(int j = 0; j <= MAX_M; ++j) { // w[i] をとる dp[i+1][j+1][1] = max(dp[i+1][j+1][1], dp[i][j][0]); // 前のをとっていない dp[i+1][j+1][1] = max(dp[i+1][j+1][1], dp[i][j][1] + w[i]); // 前のをとっている // w[i] をとらない dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][0]); // 前のをとっていない dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][1]); // 前のをとっている } if(t == 1){ if(i == n-1) ans = max(ans, dp[i][m][t]+w[n-1]); else if(i != n) ans = max(ans, dp[i][m][t]); } else { ans = max(ans, dp[i][m][t]); } } if(t == 0) ans = max(ans, dp[n][m][0]); } return ans; } inline int rand(int l, int r){ int w = r - l + 1; return rand() % w + l; } #define rep(i,n) for(int i = 0; i < (int)(n); i++) int main(){ int n,m; while(cin >> n >> m){ vector<int> w(n); rep(i,n) cin >> w[i]; assert(MIN_N <= n && n <= MAX_N); assert(MIN_M <= m && m <= MAX_M); rep(i,n) assert(MIN_W <= w[i] && w[i] <= MAX_W); int res = solve(w,m); cout << res << endl; // int exp = naive(w,m); // if(exp != res){ // cout << n << ' ' << m << endl; // for(int i = 0; i < n; i++){ // cout << w[i] << ' '; // } // cout << endl; // cout << "res = " << res << endl; // cout << "exp = " << exp << endl; // abort(); // } // return 0; } }