题解 P1987 【摇钱树】

· · 题解

感觉现有的两篇题解都没有严格证明为什么要按照p从大到小排序，所以我就写了这篇题解。

广告：https://llf0703.com

方法

贪心+dp。贪心策略是按P从大到小排序，然后01背包决定砍不砍即可。贪心证明如下：

假设最初的顺序是 A[1],A[2],...,A[x],A[x+1],...,A[n] 及 P[1],P[2],...,P[x],P[x+1],...,P[n]

对于第 x 和第 x+1 棵树，砍了它们获得的利益和 W1 是

A[x]-P[x]\times (x-1)+A[x+1]-P[x+1]\times x

如果我们交换第 x 和第 x+1 棵树，利益和 W2 就变成了

A[x]-P[x]\times x+A[x+1]-P[x+1]\times (x-1)

肯定是有更多利益我们才会交换，所以需要满足

W2-W1=P[x+1]-P[x]>0 $$即 $$ P[x+1]>P[x]

交换后就是 P[x]>P[x+1] 了，所以按照p从大到小排序。

剩下的就是标准01背包，由于数据不大，用不用滚动数组都可以。方程式是：

f[i][j]=\max \begin{cases} f[i-1][j] \\ f[i-1][j-1]+\max(0,A[i]-P[i]*(j-1)) \end{cases}

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,k,f[1005][1005],ans;
struct pig{
    int a,p;
} s[1005];

inline bool cmp(pig x,pig y)
{
    return x.p>y.p;
}

int main()
{
    while (~scanf("%d%d",&n,&k) && n && k)
    {
        memset(f,0,sizeof(f));
        ans=0;
        if (k>n) k=n;
        for (int i=1;i<=n;i++) s[i].a=read();
        for (int i=1;i<=n;i++) s[i].p=read();
        sort(s+1,s+n+1,cmp);
        for (int i=1;i<=n;i++)
            for (int j=k;j;j--)
                f[i][j]=max(f[i-1][j-1]+max(0,s[i].a-s[i].p*(j-1)),f[i-1][j]);
        for (int i=1;i<=k;i++) ans=max(ans,f[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}