BOJ 7579アプリケーション

https://www.acmicpc.net/problem/7579
時間1秒、メモリ128 MB
input :

NとM(1≦N≦100,1≦M≦1000000)

N個の整数、メモリバイト数m 1,...,mN(1 ≤ m1, ..., mN ≤ 10,000,000)

行目の整数は、各アプリケーションを無効にするコストc 1,...,cN(0 ≤ c1, ..., cN ≤ 100)

output :
無効なアプリケーションを計算して

メモリMバイトを取得する最低コスト、1行出力

条件:

N個のアプリケーション、A 1、...、ANを有効にする

アクティブなアプリケーションA 1,...,

複数のANを無効にしてより多くのMバイトのメモリを取得する必要がある

が無効になったときのコストciの和を最小限に抑えることにより、必要なメモリMバイトを得る方法

.
まず、グリディのように見えます.しかし、メモリの大きいものを無条件に見つけることはできないので、グリディは外すべきだ.
それがTwo pointer?できない
だからDPを使います.
ローがアクティブなアプリケーションの場合、カラムには各コストの最大保証バイトが格納されます.
dp[i][j]にjコストを格納し、iアプリケーションをクリアしたときにどれだけのメモリを得ることができるか.
したがって、dp[i-1][j-now cost]i-1アプリケーションをクリアすると、取得した最大メモリに現在削除されているメモリを加えて記憶する.
リファレンス
1)appの数で行を作成し、sum(cost)で列を作成します.
2)順番に迂回し、以下のアルゴリズムを実行する.
3-0)現在のアプリケーションのコストがjより大きい場合、閉じることができないため、アクティブにします.
dp[i][j] = dp[i-1][j]
3-1)そうでない場合、現在のアプリケーションを閉じたbyteとそうでないbyteに、dpに大きな値を入力します.
dp[i][j] = max(byte + dp[i-1][j-cost], dp[i-1][j])
4)現在のdp[i][j]の値がMより大きい場合、現在のコスト、jおよび以前の結果よりも小さい値をとる.
説明をこう書きます...はい

import sys

n, m = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
cost = list(map(int, sys.stdin.readline().split()))

limit = sum(cost) + 1
dp = [[0] * limit for i in range(n + 1)]

ans = 999999999

for i in range(1, n + 1):
    now_data, now_cost = data[i - 1], cost[i - 1]

    for j in range(limit):
        if j >= now_cost:
            dp[i][j] = max(now_data + dp[i - 1][j - now_cost], dp[i - 1][j])

            if dp[i][j] >= m:
                ans = min(ans, j)
        else:
            dp[i][j] = dp[i - 1][j]
print(ans)