結果

問題 No.209 Longest Mountain Subsequence
ユーザー rpy3cpprpy3cpp
提出日時 2015-05-15 23:31:48
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,331 bytes
コンパイル時間 99 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-07-06 04:18:22
合計ジャッジ時間 2,746 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 129 ms
10,752 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def read_data():
    N = int(input())
    As = list(map(int, input().split()))
    return N, As

def solve(N, As):
    if N <= 2:
        return N
    dp1 = longest_increasing(N, As)
    As.reverse()
    dp2 = longest_increasing(N, As)
    dp2.reverse()
    return max(d1 + d2 - 1 for d1, d2 in zip(dp1, dp2))
        
def longest_increasing(N, As):
    ''' As の部分列で、b0 < b1 < b2... b1 - b0 < b2 - b1 < ... となるものを返す。
    dp[i] には、As[:i]　および As[i] を用いてできる部分列の中で最長のものの長さを入れる。
    ただし、As[i] を終端に必ず用いるものとする。
    '''
    dp = []
    for i in range(N):
        dp.append(longest_inc(As[:i+1]))
    return dp

def longest_inc(As):
    '''
    '''
    bs = As[::-1]
    bs = [bs[0]] + [b for b in bs if b < bs[0]]
    return longest_dec(bs)

def longest_dec(bs):
    n = len(bs)
    dp = [0] * n
    gap = [0] * n
    dp[0] = 1
    gap[0] = float('inf')
    for i, b in enumerate(bs[1:], 1):
        for j in range(i-1, -1, -1):
            if b < bs[j] < gap[j] + b:
                gap[i] = bs[j] - b
                dp[i] = dp[j] + 1
                break
    return max(dp)

if __name__ == '__main__':
    T = int(input())
    for t in range(T):
        N, As = read_data()
        print(solve(N, As))
0