P1048 [NOIP2005 普及组] 采药
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;
}