image.png
image.png
分析
这个题目实际上是M段最大子段和的变式
可以通过动态规划来做
dp[i][j]代表共取 i 次菜，当前取完第 j 个菜时，最大的好吃程度之和
所以d[i][j] 有两个选择
- 选择以当前j为最后新开的一段的首，即与之前的段不连续，之前共有i-1段，则当前d[i][j] = Max(d[i-1][k])+A[j] k = i - j-1;
- 当前j添加到最后一段的末尾
d[i][j] = d[i][j-1] + A[j];
以上两种方法的结果取最大的那个
public class Cookie {
public static int get(int[] A,int M){
int N = A.length;
int dp[][] = new int[2][N];
//滚动数组
//记录两行
for(int i = 0; i < N;i++){
dp[0][i] = 0;
dp[1][i] = 0;
}
//算出M = 1的一行
int nowMax = Integer.MIN_VALUE;
for(int i = 0; i < N;i++) {
if (nowMax < 0) {
nowMax = A[i];
} else {
nowMax = nowMax + A[i];
}
dp[1][i] = nowMax;
}
// M > 1时，利用滚动数组减少存储空间
for(int i = 2,k = 0; i <= M; i++,k^=1){
int beforeLineMax = Integer.MIN_VALUE;
dp[k][i-2] = Integer.MIN_VALUE;
for(int j = i-1; j < i + N - M;j++){
beforeLineMax = Integer.max(beforeLineMax,dp[k^1][j-1]);
dp[k][j] = Integer.max(beforeLineMax,dp[k][j-1])+A[j];
}
}
int res = Integer.MIN_VALUE;
//得到当前第M行的最大值
for(int i = M; i < N ;i++){
res = Integer.max(res,dp[M&1][i]);
}
return res;
}
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int A[] = new int[N];
for(int i = 0; i < N;i++){
A[i] = sc.nextInt();//保存菜品
}
System.out.println(get(A,M));
}
}
过程分析
备注（列号1对应下标为0）
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| M=0 | 1 | 2 | 3 | -2 | 3 | -10 | 3 |
| M=1 | 1 | 3 | 6 | 4 | 7 | -3 | 3 |
| M=2 | 3 | 6 | 4 | 9 | -1 | 10 |
过程
image.png
d[i][j]相当于同一行的前一格子+当前格子或者前一行（i~j-1）+当前格子的最大值
