ABC128-D_equeueをpythonで解いた（その他）

問題

• ABC128-equeue

問題概要

宝石が$N$個横一列に並んでいる。
以下の４操作を$K$回まで行う。

• 操作A: 左端の宝石を取る。
• 操作B: 右端の宝石を取る。
• 操作C: 持っている宝石から１個左端に置く。
• 操作D: 持っている宝石から１個右端に置く。

方針

• 全探索すると、$O(4^K)$なので厳しい。
• 操作C、Dは持っている宝石どれを置いてもよいので、先に操作A、Bをしてから操作C,Dをすれば良いのでは？$\rightarrow$実際正解。

解法

• 左から$l$個、右から$r$個取り出し、どの宝石を戻すのかを探る。
• 宝石の価値がマイナスになっているものを戻せばよい（ソートすればわかる）。

コード

N,K = map(int,input().split())
V = list(map(int,input().split()))

ans = -1

for l in range(N+1):
    for r in range(N+1):
        tmp = V[:l] + V[N-r:]
        if l+r > N:
            break
        res = K - (l+r)
        if res < 0:
            break
        tmp.sort()
        for i in range(min(res,len(tmp))):
            if tmp[0] < 0:
                tmp.pop(0)
            else:
                break
        ans = max(ans,sum(tmp))
            
print(ans)

written by 友達のtaniponyo