結果
問題 | No.127 門松もどき |
ユーザー |
![]() |
提出日時 | 2019-05-24 00:12:58 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 114 ms / 5,000 ms |
コード長 | 1,417 bytes |
コンパイル時間 | 657 ms |
コンパイル使用メモリ | 98,612 KB |
実行使用メモリ | 86,272 KB |
最終ジャッジ日時 | 2024-09-17 09:55:59 |
合計ジャッジ時間 | 2,680 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #define popcount __builtin_popcount using namespace std; typedef long long ll; typedef pair<int, int> P; int n; int a[3001]; int dp[3001][3001], mx[2][3001][3001]; void solve(int l, int r){ if(l>=r) return; if(dp[l][r]>=0) return; solve(l+1, r); solve(l, r-1); if(a[l]==a[r]){ dp[l][r]=0; mx[0][l][r]=mx[0][l][r-1]; mx[1][l][r]=mx[1][l+1][r]; }else if(a[l]<a[r]){ dp[l][r]=max(2, 1+mx[1][l+1][r]); mx[0][l][r]=max(mx[0][l][r-1], dp[l][r]); mx[1][l][r]=mx[1][l+1][r]; }else{ dp[l][r]=max(2, 1+mx[0][l][r-1]); mx[0][l][r]=mx[0][l][r-1]; mx[1][l][r]=max(mx[1][l+1][r], dp[l][r]); } } int main() { cin>>n; bool nuo=1; for(int i=0; i<n; i++){ cin>>a[i]; if(i>0 && a[i]!=a[0]) nuo=0; } if(nuo){ cout<<1<<endl; return 0; } for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) dp[i][j]=-1; solve(0, n-1); int ans=2; for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) ans=max(ans, dp[i][j]); cout<<ans<<endl; return 0; }