这条题目是一条很简单的01背包的题目,因为每一种草药只有一株。 定义dp_{i,j}为容积为j的背包装前i个物品能获得的最大价值。对于每个物品,只有取和不取两种状态。
#include<cstdio>
#include<algorithm>
using namespace std;
int t,m,p[101],v[101],dp[101][1001];
int main(){
scanf("%d %d",&t,&m);
for(int i=1;i<=m;i++) scanf("%d %d",&p[i],&v[i]);
for(int i=1;i<=m;i++){
for(int j=1;j<=t;j++){
dp[i][j]=dp[i-1][j];//不取
if(j>=p[i])dp[i][j]=max(dp[i][j],dp[i-1][j-p[i]]+v[i]);//取
}
}
printf("%d",dp[m][t]);
return 0;
}
对不起,我写错了,应该是
定义dp_i,j为j的时间前i个草药能采到的最大价值
比赛已结束。