洛谷P1048 [NOIP 2005 遍及组] 采药

P1048 [NOIP 2005 遍及组] 采药

设 dp[j] 体现前i个物品容量不大于j的最大代价
w 体现第i个物品的代价
v 体现第i个物品的容量
那么思量 dp[j] 的取值:
1.没取第i件物品
那就和上一个物品 ( dp[i-1][j] ) 一样的代价

1. dp[i][j]=dp[i-1][j];

复制代码

2.取了第i件物品
那就在上一个物品 ( dp[i-1][j] ) 的根本上在减去i的体积 v,加上i的代价 w

1. dp[i][j]=dp[i-1][j-v[i]]+w[i];

复制代码

然后取最大代价

1. dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);

复制代码

别的，由于这题的特殊性，我们可以选择当 j < v 的时间直接

1. dp[i][j]=dp[i-1][j];

复制代码

由于当容量 j 小于这个物品的体积 v 时，这个东西肯定装不下，以是直接赋值就好了
末了答案直接输出dp[m][t]即可
ACcode:

[code]#includeusing namespace std;const int N=1005,M=105;int t,m;int dp[M][N],w[M],v[M]; //这里时间等价于容量int main(){        cin>>t>>m;        for(int i=1;i>v>>w;        for(int i=1;i=0;j--){                        if(j