毒瘤dp求教

常规
1

最大能量值

题目描述

给定长度为 n 的整数数组 a 和一个正奇数 $k$，要求在数组中从左到右依次选择 k 个互不重叠的连续子数组，令其中第 i 个连续子数组内的数字和为 $sum_i$，则这 k 个连续子数组所产生的能量值为

  • \displaystyle sum_1 \times k - sum_2 \times (k-1) + sum_3 \times (k-2) - ...+ sum_k \times 1

即 $\displaystyle \sum\limits_{i=1}^k (-1)^{i+1}\times sum_i\times(k-i+1)$。

请你求出可以得到的最大能量值。

选出来的所有连续子数组不需要覆盖整个数组，且不能为空。

输入格式

第一行两个数字 $n, k$。

第二行是 n 个整数，表示数组 $a$。

输出格式

一个整数，表示可以得到的最大能量值。

样例 #1

样例输入 #1

5 3
1 2 3 -1 2

样例输出 #1

22

样例 #2

样例输入 #2

5 5
12 -2 -2 -2 -2

样例输出 #2

64

样例 #3

样例输入 #3

3 1
-1 -2 -3

样例输出 #3

-1

提示

  • 1\leq k\leq n\leq 10^4

  • 1\leq n\times k \leq 10^6

  • 1\leq |a_i|\leq 10^9
    是洛谷的题，放心，团队自创没题解的

2 个赞
2

正解不会，写了个半优的，n^2*k

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,vis[1001][1001],a[10001],b[10001],ans=0;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=b[i-1]+a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=0;k<=i;k++){
				vis[i][j]=max(vis[k][j-1]+(b[i]-b[k-1])*j*(long long)pow(-1,j+1),vis[i-1][j]);
			}
		}
	}
	cout<<vis[n][m];
}

但是不对，大佬求切掉这道

2 个赞
3

@吴铭杨 教？

3 个赞
4

我也只会写O(n^2 k)啊，正解听不懂啊

3 个赞
5

我就是要n^2 k

3 个赞
6

坏了，xiachi的笔记忘了，咋写来着（课上的代码没保存） :grimacing:

3 个赞
7

你把我代码复制一遍？

2 个赞
8

我只是回复你啊，没说这是我的代码啊

3 个赞