牛客--布置会场（动态规划）--计算最大能获得的分数（贪心）

1.动态规划

importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){// 最大椅子数量为 30，创建数组存储方案数intmaxN=30;// ways[i] 表示 i 个椅子的合法摆放总方案数long[]ways=newlong[maxN+1];// ===================== 初始化边界条件 =====================// 1个椅子：只能放A（B无法成对），只有1种方案ways[1]=1;// 2个椅子：AA、BB，共2种方案ways[2]=2;// ===================== 动态规划递推计算 =====================// 递推公式：ways[i] = 结尾放A的方案数 + 结尾放BB的方案数// 结尾放A = ways[i-1]，结尾放BB = ways[i-2]//注意是小于等于for(inti=3;i<=maxN;i++){ways[i]=ways[i-1]+ways[i-2];}// ===================== 处理输入输出 =====================Scannerscanner=newScanner(System.in);// 读取测试用例数量inttestCount=scanner.nextInt();// 循环处理每一组测试用例while(testCount>0){// 读取当前椅子数量intchairNum=scanner.nextInt();// 输出对应方案数System.out.println(ways[chairNum]);testCount--;}// 关闭扫描器scanner.close();}}

2.暴力解法

无法过用例

3.最大能获得的分数

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();int[]arr=newint[n];//输入图形的大小for(inti=0;i<n;i++){arr[i]=sc.nextInt();}inttotal=0;//但是这里注意的是。//每次合并之后，下一个要继承合并，，所以需要一个中间值inttemp=0;//从左向右逐个合并 n个数字合并n-1次（）//然后这里要再注意下。防止下标越界//1 2 3//1 +2 =3//score 0+1*2=2//3+3=6//score= 2+3*3=11for(inti=0;i<n-1;i++){//这里先存储temp=arr[i]+arr[i+1];//计算当前的总得分total+=arr[i]*arr[i+1];//最后把前面的数字作为一个存下来--//这是一个隐形的隐藏条件，题目里没说，但是就是这样的arr[i+1]=temp;}System.out.print(total);}}