Maximum-Cup 2018 D Many Go Round(1)

ひとりぼっちの〇〇生活のカコちゃんがぼっちーの友達になりましたね。えぬわいです。

qiita.com

続き。

atcoder.jp

難しくなってきたなぁという気持ち。

1 日でなんとかするのは、きつい時期なのかなと。

DPを書く前に普通に再帰関数だけ書いてみてみる。

N, M, L, X = map(int, input().split())
a = [int(i) for i in input().split()]

def rec(pos, w):
    if pos == N:
        if w == 0:
            return True
        return False
    ans = rec(pos+1, w)
    if w-a[pos] >= 0:
        ans = ans or rec(pos+1, w-a[pos])
    return ans

sw = False
for i in range(X-1):
    if rec(0, i*M+L):
        print('Yes', i*M+L)
        break
else:
    print('No')

厳しいぜ。DPした時の計算量は、全然間に合わない。ちょろっと解答を見たんだけど、どうやら、O(NM)に落とせるらしい。明日は、O(NM)に落として書いてみる。

勉強は、集中力と時間の確保！！！