企业官网建设流程全解析

Day 11

游游的水果大礼包

解题思路：

• 直接枚举其中一个礼包的所有可能数量，可以在 O(n) 内计算出价值最高的礼包组合；
• 注意：使用贪心，算价值更大的礼包，最大数量下的组合，并不能算出最大价值礼盒，如（100,100,100,101），使用贪心得到的结果：50 个二号礼包 = 50 * 101 = 5050，最优解是： 33 *100 + 33 * 101 = 6633

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);longn=in.nextLong(),m=in.nextLong(),a=in.nextLong(),b=in.nextLong();System.out.println(cnt(n,m,a,b));}privatestaticlongcnt(longn,longm,longa,longb){longret=0;for(longi=0;i<=Math.min(n/2,m);i++){longapp=n-i*2;longpea=m-i;ret=Math.max(ret,i*a+Math.min(app,pea/2)*b);}returnret;}}

买卖股票的最好时机(二)

动态规划：

• 定义状态表示，f[i], g[i]分别为在 i 天买入，卖出的最大收益；
• 在遍历数组的过程中，不断通过各自的情况，更新对应的表；
• 注意：初始化问题，g[1] 表示第一天卖出，不可能，所以是 0；f[1] 表示第一天买入，所以是 -num[1]

importjava.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intn=in.nextInt();int[]nums=newint[n+1];for(inti=1;i<=n;i++)nums[i]=in.nextInt();// 在 i 天买入、卖出的最大收益int[]f=newint[n+1];int[]g=newint[n+1];f[1]=-nums[1];for(inti=2;i<=n;i++){f[i]=Math.max(f[i-1],g[i-1]-nums[i]);g[i]=Math.max(g[i-1],f[i-1]+nums[i]);}System.out.println(g[n]);}}

贪心

• 当前股票售价比前一支高，就减去他们的差值
• 1 2 3，结果 3 - 1 = (2-1) + (3-2)

importjava.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intn=in.nextInt();int[]nums=newint[n+1];for(inti=1;i<=n;i++)nums[i]=in.nextInt();intret=0;// 1 2 3for(inti=2;i<=n;i++){intp=nums[i]-nums[i-1];if(p>0)ret+=p;}System.out.println(ret);}}

倒置字符串

用列表手机字符串，再反转列表，最后拼接为字符串即可

importjava.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);List<String>list=newArrayList<>();while(in.hasNext())list.add(in.next());Collections.reverse(list);System.out.println(String.join(" ",list));}}