結果
問題 | No.127 門松もどき |
ユーザー |
![]() |
提出日時 | 2015-01-14 02:43:37 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 87 ms / 5,000 ms |
コード長 | 1,463 bytes |
コンパイル時間 | 1,084 ms |
コンパイル使用メモリ | 82,196 KB |
実行使用メモリ | 73,856 KB |
最終ジャッジ日時 | 2024-12-23 21:51:35 |
合計ジャッジ時間 | 2,903 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include <iostream> #include <vector> #include <cstdio> #include <sstream> #include <map> #include <string> #include <algorithm> #include <queue> #include <cmath> using namespace std; int main(){ int n; cin >> n; vector<int> a(n+2, 0); for(int i=0; i<n; i++) cin >> a[i+1]; vector<int> l = a; sort(l.begin(), l.end()); l.erase(unique(l.begin(), l.end()), l.end()); for(int i=0; i<=n; i++){ a[i] = lower_bound(l.begin(), l.end(), a[i]) - l.begin(); } //vector<int> b(a.rbegin(), a.rend()); int ans = 0; vector<vector<int>> dp_l(n+2, vector<int>(n+2, 0)); vector<vector<int>> dp_r(n+2, vector<int>(n+2, 0)); //dp_l[1][n+1] = dp_l[0][n] = 1; //dp_r[1][n+1] = dp_r[0][n] = 1; for(int i=1; i<=n; i++){ //lを場所iまで選んでいる for(int j=n; j>=i; j--){ //rを場所jまで選んでいる //rとなるものを選ぶ if(a[i] < a[j]){ dp_r[i][j] = max(max(dp_r[i-1][j], dp_r[i][j]), dp_l[i][j+1]+1); }else{ dp_r[i][j] = max(dp_r[i-1][j], dp_r[i][j]); } //lとなるものを選ぶ if(a[i] > a[j]){ dp_l[i][j] = max(max(dp_l[i][j+1], dp_l[i][j]), dp_r[i-1][j]+1); }else{ dp_l[i][j] = max(dp_l[i][j+1], dp_l[i][j]); } } } for(int i=0; i<dp_l.size(); i++){ for(int j=0; j<dp_l[i].size(); j++){ ans = max(ans, dp_l[i][j]); ans = max(ans, dp_r[i][j]); } } //どこかミスってて答えが1小さくになってしまう。謎。 cout << ans+1 << endl; return 0; }