题面

题目描述

果园里有 $N$ 棵果树，每天你可以选择一棵树将树上的果子摘完，获益就是树上果子的重量。但是每过一天第 $i$ 棵树上的果子会由于各种原因减少，导致重量下降 $p[i]$（当然，如果树上的果子为 $0$ 了，自然获利就是 $0$），问 $K$ 天内你的最大获利。

输入

共三行： 第一行两个数 $N、K$； 第二行 $N$ 个数表示树的初始重量 $a[i]$； 第三行 $N$ 个数表示 $p[i]$。

输出

仅一行一个数，表示最大获利。

样例输入

2 2 10 10 1 2

样例输出

19

提示

【数据规模】 对于 $30\%$ 的数据，满足 $1\le n\le 100$； 对于$100\%$的数据，满足$1\le n\le 1000,初始重量\le 100000$。 其中$10\%$的数据，满足$n=k$

---

题目分析

这道题类似于摇钱树 只需要在排序后做一个 $01$ 背包就可以了 （然而比赛时一直没想出来） 方程式是： $f[i][j]=max\{\begin{array}{l}f[i-1][j]\\ f[i-1][j-1]+max(x[i]-y[i]\ast (j-1),0))\end{array}$

这里我用了滚动数组，那么方程式就是： $f[j]=max(f[j],f[j-1]+max(x[i]-y[i]\ast (j-1),0))$

$code$

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct node{ int x,y; }a[1039]; int f[1039]; int n,k,ans; inline bool cmp(node i,node j){ if(i.y!=j.y) return i.y>j.y; return i.x>j.x; } int main(){ register int i,j; scanf("%d%d",&n,&k); memset(f,0,sizeof(f)); for(i=1;i<=n;i++) scanf("%d",&a[i].x); for(i=1;i<=n;i++) scanf("%d",&a[i].y); sort(a+1,a+n+1,cmp); for(i=1;i<=n;i++) for(j=max(k,i);j>0;j--) f[j]=max(f[j],f[j-1]+max(a[i].x-a[i].y*(j-1),0)); for(i=1;i<=k;i++) ans=max(ans,f[i]); printf("%d",ans); return 0; }