题解 | #采药#

#include <iostream>
using namespace std;

int t[105];
int v[105];
int dp[1005][1005];
int main() {
    int T,M;
    while(cin>>T>>M){
        for(int i=1;i<=M;i++){
            cin>>t[i]>>v[i];
        }
        for(int i=0;i<=M;i++){
            dp[i][0] = 0;
        }
        for(int j=0;j<=T;j++){
            dp[0][j] = 0;
        }
        for(int i=1;i<=M;i++){
            for(int j=1;j<=T;j++){
                if(j<t[i]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-t[i]]+v[i]);
                }
            }
        }
        cout<<dp[M][T]<<endl;
    }

}
// 64 位输出请用 printf("%lld")