【題解】TIOJ 2181 . 表演節目 (Show)

#include <iostream>
using namespace std;

int a, n, dp[1005][1005];

int main() {
    cin >> a >> n;
    for (int i = 1, x, y; i <= n; i++){
        cin >> x >> y;
        for (int j = a; j >= y; j--){
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-y]+x);
        }
        for (int j = y-1; j >= 0; j--){
            dp[i][j] = dp[i-1][j];
        }
    }
    int mx = 0, cost = 0;
    for (int i = 0; i <= a; i++){
        if (dp[n][i] > mx){
            mx = dp[n][i];
            cost = i;
        }
    }
    cout << mx << " " << cost << "\n";
}