上海企业扶持政策,洛阳400电话洛阳网站seo,浏阳网站建设hnktwl,如何做自己的网站赚钱P1659 养猪 题目描述 你有一个猪圈#xff0c;有N头猪#xff0c;每天你最多可以杀一头猪卖钱#xff0c;获益就是猪的体重。但是每过一天每头猪的体重都会下降P[i]#xff08;当然#xff0c;如果猪体重0了#xff0c;自然获利为0#xff09;#xff0c;问K天内你… 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. 输出格式 一行一个数表示最大获利。 输入输出样例 输入样例#12 2
10 10
1 2 输出样例#119 //01背包问题可以化为一维
#includeiostream
#includecstdio
#includealgorithmusing namespace std;int n,k,d[1005],ans;
struct data{int w,p;
}pig[1005];bool cmp(data a,data b)
{ if(a.pb.p)return a.wb.w;return a.pb.p; }int main()
{scanf(%d%d,n,k);for(int i1;in;i)scanf(%d,pig[i].w);for(int i1;in;i)scanf(%d,pig[i].p);sort(pig1,pig1n,cmp);//由于题的特殊性需要先将猪按掉价速度排序再dp for(int i1;in;i)for(int jmax(k,i);j1;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)(v1,wmax(pig[i].w-pig[i].p*(j-1),0))ansd[k];for(int ik;i1;i--)ansmax(ans,d[i]);//由于pig[i].w-pig[i].p*(j-1)j越小单个猪的贡献越大并且已经按掉价速度排序有时越靠前所得收益越大需要扫一遍 printf(%d\n,ans);//输出 return 0;
} 转载于:https://www.cnblogs.com/lyqlyq/p/7107330.html
