题解 | #[NOIP2005]采药#
[NOIP2005]采药
https://ac.nowcoder.com/acm/problem/16650
本题是一个01背包问题。其中时间其实就相当于背包问题里面的重量。
那么可以建立一个二维数组dp[i][j]表示对于第i个药草，时间为j来说它的最大价值。那么它的最大价值有选与不选两种情况，如果不选那么就是上一个药草，时间为j所对应的最大价值、如果选就是上一个药草对于j-a[i].tm的时间的最大价值加上这个药草的价值。在这两种情况下取最大值即可。
#include <bits/stdc++.h>
using namespace std;
struct Node {
int tm, value;
};
const int maxn = 100+10;
int dp[maxn][1000+10];
Node a[maxn];
int t, m;
int main() {
cin>>t>>m;
for (int i=1;i<=m;i++) {
cin>>a[i].tm>>a[i].value;
}
for (int i=1;i<=m;i++) {
for (int j=0;j<=t;j++) {
if (j>=a[i].tm)
dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i].tm]+a[i].value);
else
dp[i][j] = dp[i-1][j];
}
}
cout<<dp[m][t];
return 0;
}
滚动数组对于空间的优化：
由于某一个药草的情况其实只取决于上一个药草的情况，那么就可以用滚动数组直接覆盖的做法。要注意得从大到小进行计算，不然前面小的计算出来会影响后面大的结果。
#include <bits/stdc++.h>
using namespace std;
struct Node {
int tm, m;
};
int dp[1000+10];
Node a[100+10];
int t, m;
int main() {
cin>>t>>m;
for (int i=1;i<=m;i++) {
cin>>a[i].tm>>a[i].m;
}
for (int i=1;i<=m;i++) {
for (int j=t;j>=a[i].tm;j--){
dp[j] = max(dp[j], dp[j-a[i].tm]+a[i].m);
}
}
cout<<dp[t];
return 0;
}
