P1616 疯狂的采药 题解

Dworry · 2021-05-14 00:02:30 · 个人记录

刚学dp不久的小蒟蒻前来报到

看到题解里很多dalao都用了压维来节省空间。作为一个出生牛犊不怕虎的萌新（其实是不会压），一次又一次地尝试如何开二维数组不 MLE，最后终于成功了！！！(不会吧，不会吧，不会真有人做出一道橙题就开心到来发题解吧。)

在做题中，我拿过80分、90分、直到最后AC。接下来，我也会按照80分代码、90分代码、AC代码的顺序进行讲解。

一、80分代码：部分背包问题

当我第一次看到题目的时候：每种药可以无限次采摘。诶！这不就是部分背包嘛（这时候我还没有意识到问题的严重性），贪心算法走起！于是乎有了以下代码：

#include<bits/stdc++.h>
using namespace std;

struct node{
    int value;
    int cost;
    double cp;
} drug[10003];

bool cmp(node x, node y){
    return x.cp>y.cp;
}

int main(){
    int n,t;
    cin>>t>>n;
    for(int i=1;i<=n;i++){
        cin>>drug[i].cost>>drug[i].value;
        drug[i].cp=(double)drug[i].value/drug[i].cost;
    }
    sort(drug+1,drug+n+1,cmp);
    long long ans=0;
    for(int i=1;i<=n;i++){
        int get=t/drug[i].cost;
        t-=(drug[i].cost*get);
        ans+=(get*drug[i].value);
    }
    cout<<ans;
    return 0;
}

（关于部分背包问题，不是本题的重点，而且我懒，想少打几个字，可以传送 P2240 。里面有部分背包问题的详细题解，在此不展开讲解。）

提交评测：80分。。。。。。

这时，我还是有点懵。于是我点开了算法标签，恍然大悟——原来这是一道 dp 题啊！

二、90分代码：01背包问题的演变

相信来做这题的小伙伴都是从 P1048 采药问题中过来的，相信大家一定很熟悉 dp 了吧，在采药问题中，每种草药只有选和不选两种情况，很容易能够得出状态转移方程如下：（做过 P1048 的小伙伴应该再熟悉不过了）

在 01 背包问题中，我们面临的问题是选还是不选；而到了现在的问题中，我们面临的问题是选多少（如果 0 也算选的话/w）。首先还是跟 01 问题一样，先选择一株草药，之后枚举 [0,t] 的时间来更新最优状态。但是，由于草药可以多次采集，因而前一状态不再是第 i-1 株草药，而是要从第 i 株草药开始。因此，状态转移方程应修正为：