题解 | #采药#

//01背包问题

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

struct mm{
    int time;
    int worth;
};

int cmp(mm m1,mm m2){
    return m1.time<m2.time;
}
int main() {
    int t,m;
    mm cc[100];
    while (cin >> t >> m) { // 注意 while 处理多个 case
        for(int i=1;i<=m;i++){
            cin>>cc[i].time>>cc[i].worth;
        }
        int dp[m+1][t+1];
        memset(dp, 0, sizeof(dp));
        sort(cc+1, cc+m+1,cmp);//排序
        for(int i=1;i<=m;i++){
            for(int j=1;j<=t;j++){
                if(cc[i].time<=j){
                    dp[i][j]=max(dp[i-1][j], dp[i-1][j-cc[i].time]+cc[i].worth);
                }else{
                    dp[i][j]=dp[i-1][j];
                }
                
            }
        }

        cout<<dp[m][t]<<endl;;
    }
}
// 64 位输出请用 printf("%lld")