Description
Now I think you have got an AC in Ignatius.L's "Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.
Given a consecutive number sequence S 1, S 2, S 3, S 4 ... S x, ... S n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S x ≤ 32767). We define a function sum(i, j) = S i + ... + S j (1 ≤ i ≤ j ≤ n).
Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i 1, j 1) + sum(i 2, j 2) + sum(i 3, j 3) + ... + sum(i m, j m) maximal (i x ≤ iy ≤ j x or i x ≤ j y ≤ j x is not allowed).
But I`m lazy, I don't want to write a special-judge module, so you don't have to output m pairs of i and j, just output the maximal summation of sum(i x, j x)(1 ≤ x ≤ m) instead. ^_^
Input
Each test case will begin with two integers m and n, followed by n integers S 1, S2, S 3 ... S n.
Process to the end of file.
Output
Output the maximal summation described above in one line.
Sample Input
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
Sample Output
6
8
题解
因为我的DP水平实在太菜了，于是打开了Kuangbin的基本DP专题
事实证明我果然是太菜了，虽然这是第一道题，应该是入门题
想了很久我仍然无法自己推出转移方程，
写点自己的理解吧，方便自己以后回顾
应该要先推一个二维的转移方程 dp[i][j] = max(dp[i][j - 1] ,dp[i - 1][k])+a[j]; (0 < k < j)
dp[i][j]代表第i组截止到j的最大值
dp[i][j - 1] + a[j] 是 a[j]加在了上一个序列的尾部
dp[i - 1][k] + a[j] (0 <k <j ) 是 a[j] 自己形成了一个新的序列
然后用滚动数组的方法优化成了一维
pre[j -1]就是前面选好的序列形成的最大值 mx 就是加上a[j]后的最大值
不知道自己理解的对不对，希望看到这里的朋友指正
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i = a; i < n; ++i)
#define sca(x) scanf("%d",&x)
#define sca2(x,y) scanf("%d%d",&x,&y)
#define sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define pri(x) printf("%d\n",x)
typedef pair<int,int> P;
typedef long long ll;
const ll inf = ;
const int INF =0x3f3f3f3f;
const int mod = 1e9+;
const int maxn =;
const int N = 1e6+;
int dp[N],pre[N],a[N];
int m,n;
int mx;
int main(){
while(sca2(m,n) != EOF){
memset(dp,,sizeof dp);
memset(pre,,sizeof pre);
for(int i = ; i <= n; i++)
sca(a[i]);
for(int i = ; i <= m; i++){
mx = -INF;
for(int j = i; j <= n ; j++){
dp[j] = max(dp[j - ],pre[j - ]) + a[j];
pre[j - ] = mx;
mx = max(mx, dp[j]);
}
}
pri(mx);
}
return ;
}