「线性DP」牛牛的旅游纪念品
牛牛的旅游纪念品
https://ac.nowcoder.com/acm/contest/24213/1016
题目描述
但是牛牛的背包有限,他只能在商店的n个物品里面带m个回去,不然就装不下了。
并且牛牛希望买到的纪念品不要太相似,所以导购小姐姐帮助牛牛把纪念品全部排成了一行,牛牛只需要让选出来要买的m个物品中任意两个的位置差都大于等于k就行了。
现在告诉你这n个物品排成一行之后的受欢迎程度(可能是负数),求牛牛带回去的m个物品的最大欢迎度之和。
输入描述
第一行三个数n,m,k
接下来一行,有n个整数,是n个物品按顺序的受欢迎程度。
输出描述
输出一个数为题目所求的最大和
样例
#1
4 2 2
2 4 -6 1
5
提示
- n≤10000,m≤100,m≤nn≤10000,m≤100,m≤nn≤10000,m≤100,m≤n,答案保证在int范围内,保证按照题目要求一定能取到m个物品
解析
-
原问题:求 n 个物品,选择 m 个合法物品,使其获得最大欢迎值
-
子问题:求前 i 个物品中,选择 m 个合法物品,使其获取最大欢迎值
-
DP 定义:前 i 个物品中,选择 m 个合法物品,获取的最大欢迎值
-
DP 方程:dp[i][j]=max(dp[i−1][j],dp[i−k][j−1]+A[i])dp[i][j] = max(dp[i-1][j], dp[i-k][j-1] + A[i])dp[i][j]=max(dp[i−1][j],dp[i−k][j−1]+A[i])
前者是选择物品 A[i] ,后者是不选择物品 A[i]
-
DP 初始化:dp[i][j]=−INFdp[i][j] = -INFdp[i][j]=−INF 、dp[0][0]=0dp[0][0]=0dp[0][0]=0
AC Code
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();int[] A = new int[10005];int[][] dp = new int[10005][105];for(int i = 0; i <= n; i++) Arrays.fill(dp[i], -1 << 30);for(int i = 1; i <= n; i++) A[i] = sc.nextInt();for(int j = 1; j <= m; j++) {for(int i = 1; i <= n; i++) {dp[i][j] = dp[i-1][j]; // 不选择物品 A[i]if(j == 1) dp[i][j] = Math.max(dp[i][j], A[i]); // 前 i 个选 1 个的情况// 不选择物品 A[i],和选择物品 A[i]if(i - k > 0) dp[i][j] = Math.max(dp[i][j], dp[i-k][j-1] + A[i]);}}System.out.println(dp[n][m]);}
}