結果
問題 | No.209 Longest Mountain Subsequence |
ユーザー |
![]() |
提出日時 | 2019-03-30 18:42:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 131 ms / 2,000 ms |
コード長 | 1,706 bytes |
コンパイル時間 | 2,611 ms |
コンパイル使用メモリ | 203,204 KB |
最終ジャッジ日時 | 2025-01-07 00:39:48 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 |
ソースコード
#include<bits/stdc++.h>using namespace std;using Int = long long;template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}template<typename T,typename U,typename... V>typename enable_if<is_same<T, U>::value!=0>::typefill_v(U &u,const V... v){u=U(v...);}template<typename T,typename U,typename... V>typename enable_if<is_same<T, U>::value==0>::typefill_v(U &u,const V... v){for(auto &e:u) fill_v<T>(e,v...);}//INSERT ABOVE HEREint solve(){int n;cin>>n;vector<int> a(n);for(int i=0;i<n;i++) cin>>a[i];auto dp=make_v<int>(2,n,n);fill_v<int>(dp,-n*2);for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)if(a[i]!=a[j])chmax(dp[a[i]<a[j]][i][j],2);for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(a[i]==a[j]) continue;for(int k=j+1;k<n;k++){if(a[j]==a[k]) continue;int cf=a[i]<a[j];int nf=a[j]<a[k];if(cf==0&&nf==1) continue;if(cf==nf){if(cf==1&&abs(a[i]-a[j])>=abs(a[j]-a[k])) continue;if(cf==0&&abs(a[i]-a[j])<=abs(a[j]-a[k])) continue;}chmax(dp[nf][j][k],dp[cf][i][j]+1);}}}int ans=1;for(int k=0;k<2;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)chmax(ans,dp[k][i][j]);cout<<ans<<endl;return 0;}signed main(){int T;cin>>T;while(T--) solve();return 0;}