首页 > 代码库 > luogu P1659 养猪 dp 好理解

luogu P1659 养猪 dp 好理解

P1659 养猪

题目描述

你有一个猪圈,有N头猪,每天你最多可以杀一头猪卖钱,获益就是猪的体重。但是每过一天每头猪的体重都会下降P[i](当然,如果猪体重<=0了,自然获利为0),问K天内你的最大获利。

输入输出格式

输入格式:

 

第一行两个数N、K;

第二行N个数,表示猪的初始重量A[i];

第三行N个数表示P[i]。

【数据规模】

对于20%的数据,满足1≤N≤20;

对于100%的数据,满足1≤N≤1000,初始重量≤10^5.

 

输出格式:

 

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

 

输入输出样例

输入样例#1:
2 2
10 10
1 2
输出样例#1:
19
//01背包问题,可以化为一维 
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int n,k,d[1005],ans;
struct data{
    int w,p;
}pig[1005];

bool cmp(data a,data b)
{    if(a.p==b.p)return a.w>b.w;return a.p>b.p;    }

int main()
{
    scanf("%d%d",&n,&k);
    
    for(int i=1;i<=n;i++)
        scanf("%d",&pig[i].w);
        
    for(int i=1;i<=n;i++)
        scanf("%d",&pig[i].p);
        
    sort(pig+1,pig+1+n,cmp);//由于题的特殊性,需要先将猪按掉价速度排序,再dp 
    
    for(int i=1;i<=n;i++)
        for(int j=max(k,i);j>=1;j--)//01背包从后往前 
            d[j]=max(d[j],d[j-1]+max(pig[i].w-pig[i].p*(j-1),0));//背包d[j]=max(d[j],d[j-v]+w)(v==1,w==max(pig[i].w-pig[i].p*(j-1),0))
            
    ans=d[k];
    for(int i=k;i>=1;i--)
        ans=max(ans,d[i]);//由于pig[i].w-pig[i].p*(j-1),j越小单个猪的贡献越大,并且已经按掉价速度排序,有时越靠前所得收益越大,需要扫一遍 
        
    printf("%d\n",ans);//输出 
    return 0;
}

 

luogu P1659 养猪 dp 好理解