結果
問題 | No.209 Longest Mountain Subsequence |
ユーザー |
|
提出日時 | 2015-05-15 23:34:34 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 1,435 bytes |
コンパイル時間 | 1,196 ms |
コンパイル使用メモリ | 161,424 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-06 04:22:04 |
合計ジャッジ時間 | 1,860 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define all(c) (c).begin(),(c).end()#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)#define rep(i,n) REP(i,0,n)#define iter(c) __typeof((c).begin())#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)#define pb(a) push_back(a)#define pr(a) cout<<(a)<<endl#define PR(a,b) cout<<(a)<<" "<<(b)<<endl#define R cin>>#define F first#define S second#define ll long longbool check(int n,int m,int x,int y){return x>=0&&x<n&&y>=0&&y<m;}const ll MAX=1000000007,MAXL=1LL<<60,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};typedef pair<int,int> P;int main() {int T;cin >> T;while(T--) {int n;cin >> n;int a[n];rep(i,n) R a[i];int ans=0;int dp[n][n],dp2[n][n];memset(dp,0,sizeof(dp));memset(dp2,0,sizeof(dp2));rep(i,n) dp[i][i]=dp2[i][i]=1;rep(i,n) {rep(j,i+1) {REP(k,i+1,n) {if(a[j]<=a[i] && a[i]<a[k] && a[i]-a[j]<a[k]-a[i]) dp[k][i]=max(dp[k][i],dp[i][j]+1);}}}for(int i=n-1; i>=0; i--) {for(int j=n-1; j>=i; j--) {for(int k=i-1; k>=0; k--) {if(a[j]<=a[i] && a[i]<a[k] && a[i]-a[j]<a[k]-a[i]) dp2[k][i]=max(dp2[k][i],dp2[i][j]+1);}}}rep(i,n) {int x=0,y=0;rep(j,n) {x=max(x,dp[i][j]);y=max(y,dp2[i][n-1-j]);}ans=max(ans,x+y-1);}cout << ans << endl;}return 0;}