結果
問題 | No.127 門松もどき |
ユーザー |
|
提出日時 | 2015-01-14 00:19:57 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 348 ms / 5,000 ms |
コード長 | 954 bytes |
コンパイル時間 | 840 ms |
コンパイル使用メモリ | 57,204 KB |
実行使用メモリ | 74,240 KB |
最終ジャッジ日時 | 2024-12-23 21:50:17 |
合計ジャッジ時間 | 6,464 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int BUF = 3005; int N, A[BUF]; void read() { cin >> N; N += 2; A[0] = A[N - 1] = -1; for (int i = 1; i < N - 1; ++i) cin >> A[i]; } int rec(bool doLeft, int L, int R, int dp[2][BUF][BUF]) { if (L > R) return 0; int &ret = dp[doLeft][L][R]; if (ret != -1) return ret; ret = 0; if (doLeft) { if (A[L] > A[R]) ret = max(ret, rec(!doLeft, L, R, dp) + 1); ret = max(ret, rec(doLeft, L + 1, R, dp)); } else { if (A[L] < A[R]) ret = max(ret, rec(!doLeft, L, R, dp) + 1); ret = max(ret, rec(doLeft, L, R - 1, dp)); } return ret; } void work() { static int dp[2][BUF][BUF]; memset(dp, -1, sizeof(dp)); cout << max(rec(0, 0, N - 2, dp), rec(1, 1, N - 1, dp)) << endl; } int main() { read(); work(); return 0; }