【題解】ZeroJudge d862: NOIP2001 4.装箱问题

#include <iostream>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N, n;
    cin >> N >> n;
    int a[n];
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    int dp[N+1] = {};
    for (int i = 0; i < n; i++){
        for (int j = N; j > a[i]-1; j--){
            dp[j] = max(dp[j], dp[j - a[i]] + a[i]);
        }
    }
    cout << N - dp[N] << "\n";
    return 0;
}

while True:
    try:
        N = int(input())
        n = int(input())
        p = []
        for i in range(n):
            p.append(int(input()))
            
        dp = [0 for i in range(N+1)]
        for i in range(n):
            for j in range(N, p[i]-1, -1):
                dp[j] = max(dp[j], dp[j - p[i]] + p[i])
        print(N - dp[N])              
    except:
        break