题解 P1987 【摇钱树】

· · 题解

贪心+DP

不会告诉你们这道题就是：养猪 (题目名)

欢迎来踩博客：five20

思路：首先，吐槽一下题目数据，没有指出Mi>=Bi，大家应该把这个当作隐藏条件。至于思路，我们先思考，很明显若只选1棵树，那就选价值最大的，若要选多棵树，则要先选消耗最大的(不一定价值最大)。为什么呢？假设我们有3棵树且要选全部，每棵价值和每次消耗分别为m1,m2,m3;b1,b2,b3;则总价值=m1+m2+m3-k1*b1-k2*b2-k3*b3，其中k为第几次选-1，很明显消耗的大的系数要小，即消耗大的要先取。以此我们可以推及到n棵树选k棵的情况(明显就是dp了嘛)，先按消耗从大到小贪心排序，这样去取肯定保证最优，然后考虑dp，设f[i][j]表示前i棵树选j棵得到的最大值，则很容易得到状态转移方程：f[i][j]=max(f[i-1][j],f[i-1][j-1]+max(0,m[i]-b[i]*(j-1))) 。

注意：价值减小到0后直接赋为0。

代码：

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define il inline
int n,k,f[1005][1005],ans;
struct pig{
int a,p;
}zhu[1005];
il bool cmp(pig a,pig b){return a.p>b.p;}
il int gi()
{
    int a=0;char x=getchar();bool f=0;
    while((x<'0'||x>'9')&&x!='-')x=getchar();
    if(x=='-')x=getchar(),f=1;
    while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
    return f?-a:a;
}
il int max(int a,int b){if(a>b)return a;return b;}
int main()
{
    while(1){
        n=gi(),k=gi();
        if(n==0&&k==0)return 0;
    ans=0;
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)zhu[i].a=gi();
    for(int i=1;i<=n;i++)zhu[i].p=gi();
    sort(zhu+1,zhu+n+1,cmp);
    for(int i=1;i<=k;i++)
    for(int j=1;j<=n;j++)
    {
        int x=zhu[j].a-zhu[j].p*(i-1);
        x=x>0?x:0;
        f[j][i]=max(f[j-1][i],f[j-1][i-1]+x);
    }
    for(int i=1;i<=k;i++)ans=max(f[n][i],ans);
    printf("%d\n",ans);
    }
    return 0;
}