解题思路:
最大伤害为 大招伤害 + 打死Boss前的最大叠加伤害(<=m-1)
1. 对伤害进行排序
2. 使用动态规划求得打死Boss前的最大叠加伤害
3. 输出最大伤害
注意事项:
参考代码:
import java.util.Arrays; import java.util.Scanner; public class C1789 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(), m = sc.nextInt(); int[] a = new int[n]; for(int i = 0; i < n; i++) a[i] = sc.nextInt(); Arrays.sort(a); //最大伤害为 大招 +打死Boss前的最大叠加伤害(<=m-1)(动态规划求解) int[][] dp = new int[n-1][m]; dp[0][a[0]] = 1; for(int i = 1; i < n-1; i++){ for(int j = 1; j < m; j++){ if(a[i] == j){ dp[i][j] = 1; }else{ dp[i][j] = dp[i-1][j]; if(j >= a[i]) dp[i][j] = Math.max(dp[i][j], dp[i-1][j-a[i]]); } } } //打印动态规划dp表 /*for(int i = 0; i < n-1; i++){ for(int j = 0; j < m; j++){ System.out.print(dp[i][j] + " "); } System.out.println(); }*/ //获取打死Boss前的最大叠加伤害 int max = 0; for(int j = m-1; j >= 0 && max == 0; j--){ for(int i = n-2; i >= 0; i--){ if(dp[i][j] == 1){ max = j; break; } } } System.out.println(max + a[n-1]); } sc.close(); } }
0.0分
0 人评分
剪刀石头布 (C语言代码)不知道怎么直接在scanf中用枚举变量浏览:1318 |
淘淘的名单 (C语言代码)答案错误???浏览:595 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:867 |
P1001 (C语言代码)浏览:801 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:760 |
本人酷爱递归实现很多问题,这里也是浏览:558 |
WU-格式化数据输出 (C++代码)浏览:1212 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:530 |
sizeof的大作用 (C语言代码)浏览:1453 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:679 |