[白俊-2293]硬貨1

3176 ワード
パイ 白駿 DP テキストリンク

マイコード

import sys
input = sys.stdin.readline

n,k=map(int,input().split())
dp=[0]*(k+1)

for _ in range(n):  
    c=int(input())
    if c<=k:
        dp[c]+=1
    for i in range(c+1,k+1):
        dp[i]+=dp[i-c]
print(dp[k])

実行時間:263ミリ秒


に答える


dp[i]における硬貨値の和はiの数である.
入力された数字をcと呼ぶ場合、iはi-cの場合、cを加算するだけでよいので、dp[i]+=dp[i-c]となる.
硬貨の価値が1、2、5であれば、dp[10]=dp[9]+dp[8]+dp[5]であり、問題の構成は同じであり、順序の違いだけを見て同じであり、このような一度の処理はできない.
一つ一つ処理しなければなりません.
根掘り葉掘りload initilzeメソッド
[Ava]配列-copyOf/copyOfRangeのコピー