题面
核心思想
背包问题变种定义一个三维数组 dp[i][t][h] 表示前i个事件在时间剩余t精力剩余h的最大快乐值
每个事件考虑分享or不分享,然后取最大值
代码
import java.util.*;
public class Main {
public static void main(String[] args) {
final long MOD = (long) (1e9 + 7);
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int T = scanner.nextInt(), H = scanner.nextInt();
// 前i个事件在时间剩余t精力剩余h的最大快乐值
long[][][] dp = new long[n + 1][T + 1][H + 1];
int[][] event = new int[n][3];
for(int i = 0; i < n; i++){
int x = scanner.nextInt();
int y = scanner.nextInt();
int z = scanner.nextInt();
event[i][0] = x;
event[i][1] = y;
event[i][2] = z;
}
for(int i = 1; i <=n; i++){
for(int t = 0; t <= T; t++){
for(int h = 0; h <= H; h++){
//剩余时间
int leftT = t - event[i - 1][0];
//剩余精力
int leftH = h - event[i - 1][1];
//不分享事件i
dp[i][t][h] = dp[i - 1][t][h];
//能够分享事件i 则取最大值
if(leftT >= 0 && leftH >= 0)
dp[i][t][h] = Math.max(dp[i][t][h], dp[i - 1][leftT][leftH] + event[i - 1][2]);
}
}
}
System.out.println(dp[n][T][H]);
}
}
标签:24,scanner,nextInt,小红书,long,int,秋招,event,dp
From: https://www.cnblogs.com/ganyq/p/18123732