P1048 [NOIP2005 普及组] 采药

#include<bits/stdc++.h>
using namespace std;
long long T,M,w[105],t[105],dp[1005][1005];
int main(){cin>>T>>M;for(int i=1;i<=M;i++) cin>>t[i]>>w[i];for(int i=1;i<=T;i++){ //i表示时间限制for(int j=1;j<=M;j++){ //j表示选取药材的范围（前j个中做选择）dp[i][j]=dp[i][j-1];//j-1表示舍弃第j个,不取 if(i>=t[j]) dp[i][j]=max(dp[i-t[j]][j-1]+w[j],dp[i][j]); //取第j个药材 }}cout<<dp[T][M];return 0;	
}