結果
問題 | No.209 Longest Mountain Subsequence |
ユーザー | a |
提出日時 | 2015-05-15 22:49:21 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 203 ms / 2,000 ms |
コード長 | 1,024 bytes |
コンパイル時間 | 298 ms |
コンパイル使用メモリ | 39,636 KB |
実行使用メモリ | 8,408 KB |
最終ジャッジ日時 | 2023-09-20 08:26:47 |
合計ジャッジ時間 | 1,687 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 87 ms
8,256 KB |
testcase_01 | AC | 76 ms
8,304 KB |
testcase_02 | AC | 69 ms
8,328 KB |
testcase_03 | AC | 203 ms
8,296 KB |
testcase_04 | AC | 201 ms
8,408 KB |
testcase_05 | AC | 42 ms
8,384 KB |
ソースコード
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n; int a[111]; int dp[111][111][111]; int solve(int s,int t,int u) { if( u == n ) return 0; if( dp[s][t][u] >= 0 ) return dp[s][t][u]; int res = solve(s,t,u+1); //printf("%d %d %d\n",a[s],a[t],a[u]); if( a[s] < a[t] ) { if( a[t] < a[u] && a[t]-a[s] < a[u]-a[t] ) { res = max(res,solve(t,u,u+1)+1); } if( a[t] > a[u] ) { res = max(res,solve(t,u,u+1)+1); } } if( a[s] > a[t] ) { if( a[t] > a[u] && a[s]-a[t] > a[t]-a[u] ) { res = max(res,solve(t,u,u+1)+1); } } return dp[s][t][u] = res; } int main(void) { int t; scanf("%d",&t); while( t-- ) { scanf("%d",&n); for( int i = 0; i < n; i++ ) scanf("%d",a+i); memset(dp,-1,sizeof(dp)); int res = 1; for( int i = 0; i < n; i++ ) { for( int j = i+1; j < n; j++ ) { if( a[i] != a[j] ) { res = max(res,solve(i,j,j+1)+2); } } } printf("%d\n",res); } return 0; }