题解 | #采药#

#include <bits/stdc++.h>
using namespace std;

int dp[105][1005]; // 前i种草药在j时间里采摘
int main() {
    int T,M;
    while(cin>>T>>M){
        int time[105],value[105];
        for(int i=1;i<=M;i++) cin>>time[i]>>value[i];
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=M;i++){
            for(int j=1;j<=T;j++){
                if(time[i] > j) dp[i][j]=dp[i-1][j];
                else dp[i][j] = max(dp[i-1][j],dp[i-1][j-time[i]]+value[i]);
            }
        }
        cout<<dp[M][T]<<endl;
    }
}
// 64 位输出请用 printf("%lld")