做卖车网站需要什么手续,哪里有好的免费的网站建设,阳江网红桥定位,网页界面设计的用途有题目描述 Cpg 正在游览一个梦中之城#xff0c;在这个城市中有n棵摇钱树。。。这下#xff0c;可让Cpg看傻了。。。可是Cpg只能在这个城市中呆K天#xff0c;但是现在摇钱树已经成熟了#xff0c;每天 每棵都会掉下不同的金币#xff08;不属于Cpg#xff01;#xff09… 题目描述 Cpg 正在游览一个梦中之城在这个城市中有n棵摇钱树。。。这下可让Cpg看傻了。。。可是Cpg只能在这个城市中呆K天但是现在摇钱树已经成熟了每天 每棵都会掉下不同的金币不属于Cpg。Cpg每天可以砍掉其中一颗并获得其树上说有的金币怎么会有这种好事。。。。请你帮助Cpg算出他在这 K天中最多能获得多少金币。 输入输出格式 输入格式每个文件中有不超过10组测试数据。 每组测试数据 第一行两个整数nK (1Kn1000) 第二行n个整数Mi (Mi 100000).表示Cpg刚看到这n棵树时每刻树上的金币数。 第三行n个整数 Bi.(Bi1000)表示每颗摇钱树每天将会掉落的金币。 以nK0结束。 输出格式对每组测试数据输出仅一行Cpg在K天中能获得的最大金币数。 输入输出样例 输入样例#1 复制 3 3
10 20 30
4 5 6
4 3
20 30 40 50
2 7 6 5
0 0输出样例#1 复制 47
104 先按每天掉的苹果数量排序 然后就是01背包 f[j]max(f[j],f[j-1]max(tree[i].m-tree[i].b*(j-1),0)); 最后扫一遍输出K天内最优值即可 1 #includeiostream2 #includecstdio3 #includecstring4 #includealgorithm5 using namespace std;6 struct Node7 {8 int x,p;9 }a[1001];
10 int n,k,f[1001],ans;
11 bool cmp(Node a,Node b)
12 {
13 return a.pb.p;
14 }
15 int main()
16 {int i,j;
17 while (cinnknk)
18 {memset(f,0,sizeof(f));
19 ans0;
20 for (i1;in;i)
21 {
22 scanf(%d,a[i].x);
23 }
24 for (i1;in;i)
25 {
26 scanf(%d,a[i].p);
27 }
28 sort(a1,an1,cmp);
29 for (i1;in;i)
30 {
31 for (jmax(i,k);j1;j--)
32 {
33 f[j]max(f[j-1]max(0,-a[i].p*(j-1)a[i].x),f[j]);
34 }
35 }
36 for (i1;ik;i)
37 ansmax(ans,f[i]);
38 coutansendl;
39 }
40 } 转载于:https://www.cnblogs.com/Y-E-T-I/p/7804282.html
