結果
問題 | No.324 落ちてた閉路グラフ |
ユーザー |
![]() |
提出日時 | 2015-12-17 10:48:23 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 401 ms / 5,000 ms |
コード長 | 1,895 bytes |
コンパイル時間 | 1,109 ms |
コンパイル使用メモリ | 83,784 KB |
実行使用メモリ | 144,648 KB |
最終ジャッジ日時 | 2024-11-15 19:30:00 |
合計ジャッジ時間 | 5,439 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 |
ソースコード
#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>//#include<cctype>#include<climits>#include<iostream>#include<string>#include<vector>#include<map>//#include<list>#include<queue>#include<deque>#include<algorithm>//#include<numeric>#include<utility>#include<complex>//#include<memory>#include<functional>#include<cassert>#include<set>#include<stack>const int dx[] = {1, 0, -1, 0};const int dy[] = {0, 1, 0, -1};using namespace std;typedef long long ll;typedef vector<int> vi;typedef vector<ll> vll;typedef pair<int, int> pii;const int MAXN = 3003;const int INF = 1e9;int dp1[MAXN][MAXN][2];int dp2[MAXN][MAXN][2];int w[MAXN];int n, m;int dfs1(int now, int rest, int pre) {if (now == n) {if (rest > 0) return -INF/2;if (pre) return w[n-1];else return 0;}int& ret = dp1[now][rest][pre];if (ret > -INF) return ret;ret = dfs1(now+1, rest, 0);if (rest > 0) {int tmp = dfs1(now+1, rest-1, 1);if (pre) tmp += w[now-1];ret = max(ret, tmp);}return ret;}int dfs2(int now, int rest, int pre) {if (now==n) {if (rest > 0) return -INF/2;return 0;}int& ret = dp2[now][rest][pre];if (ret > -INF) return ret;ret = dfs2(now+1, rest, 0);if (rest > 0) {int tmp = dfs2(now+1, rest-1, 1);if (pre) tmp += w[now-1];ret = max(ret, tmp);}return ret;}int main() {cin.tie(0);ios::sync_with_stdio(false);cin >> n >> m;for (int i = 0; i < n; i++) cin >> w[i];for (int i = 0; i <= n; i++) {for (int j = 0; j <= n; j++) {for (int k = 0; k < 2; k++) dp1[i][j][k] = dp2[i][j][k] = -INF;}}// 最初の頂点を入れるint ans = dfs1(1, m-1, 1);ans = max(ans, dfs2(1, m, 0));cout << ans << endl;return 0;}