JZOJ 养猪 （dp-01背包）
来源：JZOJ
题目描述
作者：Z__X
你有一个猪圈，有 NNN 头猪，每天你最多可以杀一头猪卖钱，收益就是猪的体重。但是每过一天猪的体重都会下降 PiPiPi，问 KKK 天内你的最大获利。
解题思路 这是一道纯粹的 010101 背包，就是要处理一个细节：猪的体重会下降； 首先，要按体重下降速度排序，下降快的肯定得先处理呀，不然猪的体重就变负数了（“死”了QAQQAQQAQ） 然后，就是一个板子吧，不过状态转移方程得注意一个小细节，如果杀猪，得保证猪的体重大于 000，只要 max(a[i].a−a[i].p∗(j−1),0)max(a[i].a-a[i].p*(j-1),0)max(a[i].a−a[i].p∗(j−1),0) 这样就可以作为杀猪的代价了。 Code#include
using namespace std;
int n,k;
int f[10010];
struct node
{
int a;
int p;
}a[10010];
bool mycmp(node a,node b) //按体重下降速度排序
{
if (a.p==b.p) return a.ab.p;
}
int main()
{
freopen("pig.in","r",stdin);
freopen("pig.out","w",stdout);
scanf("%d %d",&n,&k);
for (int i=1;i<=n;i++) scanf("%d",&a[i].a);
for (int i=1;i<=n;i++) scanf("%d",&a[i].p);
sort(a+1,a+n+1,mycmp);
for (int i=1;i=1;j--) //记得在k和i之间取最大值
{
f[j]=max(f[j],f[j-1]+max(a[i].a-a[i].p*(j-1),0));
}
}
int ans=f[1];
for (int i=1;i<=k;i++) ans=max(ans,f[i]); //因为最优解可能存在于k天内的任何一天，所以要取最优质
printf("%d",ans);
return 0;
}
作者：Z__X
