题解 | #点菜问题#

#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;

int main(){
    int c,n;
     vector<pair<int,int>> price;
     while(scanf("%d%d",&c,&n) != EOF){
    for(int i = 0 ; i < n ; ++i){
        int a,b;
        scanf("%d%d",&a,&b);
        price.emplace_back(a,b);
    }
    vector<vector<int>> dp(n + 1, vector<int>(c + 1, 0));
    for(int i = 1 ; i <= n ; ++i){
        for(int  j = 1 ; j <= c ;++j){
            if(j >= price[i-1].first){
                dp[i][j] = max(dp[i-1][j],dp[i - 1][j - price[i - 1].first] + price[i - 1].second);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    printf("%d",dp[n][c]);
     }
     return 0;
}