题解：P1048 [NOIP2005 普及组] 采药

3_14 · 2025-01-15 11:53:19 · 题解

题目传送门

思路

一个典型的 0-1背包问题。我们需要在给定的时间内，选择一些草药，使得它们的总价值最大。每个草药只能选择一次（即要么采，要么不采）。

我们可以定义一个二维数组 dp_{i,j}，表示前 i 株草药在时间 j 内可以获得的最大价值。

• * 如果不采摘第 $i$ 株草药，那么 $dp_{i,j} = dp_{i-1,j}$。 * 如果采摘第 $i$ 株草药，那么 $dp_{i,j} = dp_{i-1,j-time_i} + value_i$。 * 最终 $dp_{i,j}$ 取上述两种情况的最大值。

代码

#include<bits/stdc++.h>
#define Freopen(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
#define lcm(x,y) x/__gcd(x,y)*y;
#define lb(x) (x&-x)
#define str to_string
using namespace std;
using ll=long long;
const double EPS=1e-6,PAI=acos(-1.0);
const int MAX=1e6+5;
int T,M;
int main(){
    cin >>T>>M;
    vector<int>time(M+1),value(M+1);
    vector<vector<int>>dp(M+1,vector<int>(T+1,0));
    for(int i=1;i<=M;++i)cin>>time[i]>>value[i];
    for(int i=1;i<=M;++i){
        for(int j=0;j<=T;j++){
            if(j>=time[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-time[i]]+value[i]);
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[M][T]<<'\n';
    return 0;
}

AC 记录