小O的溢出 （Java代码）

解题思路:
     最大伤害为 大招伤害 + 打死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();
	}
	
	
}