[金俊/python/1945]ギタリスト

6110 ワード
python 白駿 DP アルゴリズム#アルゴリズム# テキストリンク

質問リンク:ギタリスト
この問題は2列で解いたものだ.なぜ放送するのか!これはずっと叫んでいる問題です.かっこで書いてあったのですが、、、、

n,s,m=map(int,input().split())
song=list(map(int, input().split()))
dp=[[0]*(m+1) for _ in range(n+1)]
dp[0][s]=1 #시작음 1표시

for i in range(n):
    for j in range(m+1):
        if dp[i][j]==1:
            if j+song[i]<=m:
                dp[i+1][j+song[i]]=1
            if j-song[i]>=0:
                dp[i+1][j-song[i]]=1

answer=-1
for i in range(m, -1,-1):  #내려가며 1이 있다면 그 소리가 낼 수 있는 최대소리
    if dp[n][i]==1:
        answer=i
        break
print(answer)
歌の順番と各音を1つに並べます.配列に1が表示されている場合は、その音が可能であることを示します.
範囲を測って、演奏可能な音に1を表示し、最後に最後の歌の並びの中で1を見つけます.このとき、最高値を出すために、最高音から下がり始める.
ソートの選択
useQueryがundefinedを返すときの一時的な方法!