結果
問題 | No.209 Longest Mountain Subsequence |
ユーザー |
![]() |
提出日時 | 2020-01-04 16:20:02 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 1,717 bytes |
コンパイル時間 | 2,408 ms |
コンパイル使用メモリ | 165,072 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-22 20:48:27 |
合計ジャッジ時間 | 3,283 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define int long long#define FOR(i, a, b) for(int i=(a);i<(b);i++)#define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--)#define REP(i, n) for(int i=0; i<(n); i++)#define RREP(i, n) for(int i=(n-1); i>=0; i--)#define ALL(a) (a).begin(),(a).end()#define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end());#define CONTAIN(a, b) find(ALL(a), (b)) != (a).end()#define array2(type, x, y) array<array<type, y>, x>#define vector2(type) vector<vector<type> >#define out(...) printf(__VA_ARGS__)int dxy[] = {0, 1, 0, -1, 0};/*================================*/int T,N;int A[111];vector<vector<int>> count_dp(int A[], vector<vector<int>> DP) {REP(i,N+1)REP(j,N+1)DP[i][j]=0;REP(i,N+1)FOR(j,i,N+1)FOR(k,j+1,N+1){if (j>0 && A[k-1] <= A[j-1]) continue;if (i!=0) {int prev = A[j-1] - A[i-1];int diff = A[k-1] - A[j-1];if (diff <= prev) continue;}DP[j][k] = max(DP[j][k], DP[i][j] + 1);}return DP;}signed main(){#if DEBUGstd::ifstream in("input.txt");std::cin.rdbuf(in.rdbuf());#endifcin>>T;while(T--) {cin>>N;REP(i,N)cin>>A[i];vector<vector<int>> DP(N+1, vector<int>(N+1, 0));auto DPa = count_dp(A, DP);reverse(A, A+N);auto DPb = count_dp(A, DP);int ans = 0;FOR(i,1,N+1) {int a = 0, b = 0;REP(j,i) {a = max(a, DPa[j][i]);}REP(j,N-i+1) {b = max(b, DPb[j][N-i+1]);}ans = max(ans, a + b - 1);}cout << ans << endl;}return 0;}