結果
問題 | No.324 落ちてた閉路グラフ |
ユーザー |
![]() |
提出日時 | 2016-08-31 21:16:23 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 109 ms / 5,000 ms |
コード長 | 2,580 bytes |
コンパイル時間 | 955 ms |
コンパイル使用メモリ | 64,504 KB |
実行使用メモリ | 145,216 KB |
最終ジャッジ日時 | 2024-11-15 19:44:17 |
合計ジャッジ時間 | 5,149 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>#include <cstdio>typedef long long ll;using namespace std;#define rep(i,n) for(int i=0;i<(n);i++)int n, m;//dp1[i][j][k] := (0番目の頂点を選ばず、)i番目までを考えて、//選んだ頂点がj個でi番目の頂点をk=1の時選び、k=0の時選んでいないint dp1[3010][3010][2];//dp1[i][j][k] := (0番目の頂点を選び、)i番目までを考えて、//選んだ頂点がj個でi番目の頂点をk=1の時選び、k=0の時選んでいないint dp2[3010][3010][2];const int INF = 1e9;int main(void){cin >> n >> m;vector<int> w(n);rep(i, n) cin >> w[i];rep(i, 3010)rep(j, 3010)rep(k, 2){dp1[i][j][k] = dp2[i][j][k] = -INF;}dp1[0][0][0] = 0;for (int i = 0; i < n; ++i){for (int j = 0; j <= i + 1; ++j){for (int k = 0; k < 2; ++k){if(dp1[i][j][k] == -INF)continue;if(k == 0){//i番目の頂点を選んでいないdp1[i + 1][j + 1][1] = max(dp1[i][j][k], dp1[i + 1][j + 1][1]);//i+1番目を選ぶdp1[i + 1][j][0] = max(dp1[i][j][k], dp1[i + 1][j][0]);//i+1番目を選ばない}else{//i番目の頂点を選んでいるdp1[i + 1][j + 1][1] = max(dp1[i][j][k] + w[i], dp1[i + 1][j + 1][1]);//i+1番目を選ぶdp1[i + 1][j][0] = max(dp1[i][j][k], dp1[i + 1][j][0]);//i+1番目を選ばない}}}}dp2[0][1][1] = 0;for (int i = 0; i < n - 1; ++i){for (int j = 0; j <= i + 1; ++j){for (int k = 0; k < 2; ++k){if(dp2[i][j][k] == -INF)continue;if(k == 0){//i番目の頂点を選んでいないdp2[i + 1][j][0] = max(dp2[i][j][k], dp2[i + 1][j][0]);//i+1番目を選ばないif(i == n - 2){//0番目の頂点を選んでいるのでw[i + 1]も考えるdp2[i + 1][j + 1][1] = max(dp2[i][j][k] + w[i + 1], dp2[i + 1][j + 1][1]);//i+1番目を選ぶ}else{dp2[i + 1][j + 1][1] = max(dp2[i][j][k], dp2[i + 1][j + 1][1]);//i+1番目を選ぶ}}else{//i番目の頂点を選んでいるdp2[i + 1][j][0] = max(dp2[i][j][k], dp2[i + 1][j][0]);//i+1番目を選ばないif(i == n - 2){//0番目の頂点を選んでいるのでw[i + 1]も考えるdp2[i + 1][j + 1][1] = max(dp2[i][j][k] + w[i] + w[i + 1], dp2[i + 1][j + 1][1]);//i+1番目を選ぶ}else{dp2[i + 1][j + 1][1] = max(dp2[i][j][k] + w[i], dp2[i + 1][j + 1][1]);//i+1番目を選ぶ}}}}}int ans = -INF;rep(i, n){rep(j, 2){ans = max(ans, dp1[n - 1][m][j]);ans = max(ans, dp2[n - 1][m][j]);}}printf("%d\n", ans);return 0;}