結果
問題 | No.209 Longest Mountain Subsequence |
ユーザー | mkawa2 |
提出日時 | 2020-02-05 18:23:15 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,200 bytes |
コンパイル時間 | 258 ms |
コンパイル使用メモリ | 82,040 KB |
実行使用メモリ | 77,276 KB |
最終ジャッジ日時 | 2024-09-22 18:53:26 |
合計ジャッジ時間 | 2,003 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | MLE | - |
testcase_01 | MLE | - |
testcase_02 | MLE | - |
testcase_03 | MLE | - |
testcase_04 | MLE | - |
testcase_05 | MLE | - |
ソースコード
def main(): t=int(input()) for _ in range(t): n=int(input()) aa=list(map(int,input().split())) # dp0[i][j]...右端が...aa[j],aa[i]となる部分列の最大長 dp0=[[1]*n for _ in range(n)] for i in range(n): for j in range(i): if aa[i]<=aa[j]:continue v=2 d=aa[i]-aa[j] for k in range(j): if aa[j]-aa[k]>=d:continue if dp0[j][k]+1>v:v=dp0[j][k]+1 dp0[i][j]=v # dp1[i][j]...左端がaa[i],aa[j]...となる部分列の最大長 dp1=[[1]*n for _ in range(n)] for i in range(n-1,-1,-1): for j in range(n-1,i,-1): if aa[i]<=aa[j]:continue v=2 d=aa[i]-aa[j] for k in range(n-1,j,-1): if aa[j]-aa[k]>=d:continue if dp1[j][k]+1>v:v=dp1[j][k]+1 dp1[i][j]=v # aa[i]を頂点としたときの長さで最大を求める ans=0 for i in range(n): cur=max(dp0[i])+max(dp1[i])-1 if cur>ans:ans=cur print(ans) main()