結果
問題 | No.209 Longest Mountain Subsequence |
ユーザー |
![]() |
提出日時 | 2020-02-05 18:19:29 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,741 ms / 2,000 ms |
コード長 | 1,349 bytes |
コンパイル時間 | 263 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2024-09-22 18:45:48 |
合計ジャッジ時間 | 6,725 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 |
ソースコード
import syssys.setrecursionlimit(10 ** 6)def II(): return int(sys.stdin.readline())def LI(): return list(map(int, sys.stdin.readline().split()))def main():t=II()for _ in range(t):n=II()aa=LI()# 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]:continuev=2d=aa[i]-aa[j]dpj=dp0[j]for k in range(j):if aa[j]-aa[k]>=d:continueif dpj[k]+1>v:v=dpj[k]+1dp0[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]:continuev=2d=aa[i]-aa[j]dpj=dp1[j]for k in range(n-1,j,-1):if aa[j]-aa[k]>=d:continueif dpj[k]+1>v:v=dpj[k]+1dp1[i][j]=v# aa[i]を頂点としたときの長さで最大を求めるans=0for i in range(n):cur=max(dp0[i])+max(dp1[i])-1if cur>ans:ans=curprint(ans)main()