Max Sum Plus Plus
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 18653 Accepted Submission(s): 6129
Problem DescriptionNow
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 S1, S2, S3, S4 … Sx, … Sn (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ Sx ≤ 32767). We define a function sum(i, j) = Si + … + Sj (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(i1, j1) + sum(i2, j2) + sum(i3, j3) + … + sum(im, jm) maximal (ix ≤ iy ≤ jx or ix ≤ jy ≤ jx 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(ix, jx)(1 ≤ x ≤ m) instead. ^_^ InputEach test case will begin with two integers m and n, followed by n integers S1, S2, S3 … Sn.
Process to the end of file. OutputOutput the maximal summation described above in one line. Sample Input1 3 1 2 32 6 -1 4 -2 3 -2 3 Sample Output6
8
Hint
Huge input, scanf and dynamic programming is recommended.
dp[i][j][0] … 表示前i个数分成j个组,不选第i个数的最大得分
dp[i][j][1] … 表示前i个数分成j个组,选第i个数的最大得分
因为状态i只跟状态i-1, 所以可以用滚动数组来减空间
取最要自己写 。 否则卡常数会超时
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std ;
const int N = ;
const int inf = 1e9+;int dp[][N][] , n , m , x[N] ;
inline int MAX( int a , int b ) {
if( a > b ) return a ;
else return b ;
}
int main() {
// freopen("in.txt","r",stdin);
while( ~scanf("%d%d",&m,&n) ) {
for( int i = ; i <= n ; ++i ) {
scanf("%d",&x[i]);
}
int v = ;
dp[v][][] = ;
dp[v][][] = x[] ;
for( int i = ; i < n ; ++i ) {
for( int j = ; j <= i + && j <= m ; j++ ) {
dp[v^][j][] = dp[v^][j][] = -inf ;
}
for( int j = min( m , i ) ; j >= ; --j ) {
if( j != i ) {
dp[v^][j+][] = MAX( dp[v][j][] + x[i+] , dp[v^][j+][] );
dp[v^][j][] = MAX( dp[v][j][] , dp[v^][j][]);
}
if( j != ) {
dp[v^][j][] = MAX ( dp[v^][j][] , dp[v][j][] + x[i+] ) ;
dp[v^][j+][] = MAX ( dp[v^][j+][] , dp[v][j][] + x[i+] ) ;
dp[v^][j][] = MAX ( dp[v^][j][] , dp[v][j][] ) ;
}
}
v ^= ;
}
int ans = -inf ;
if( m < n ) ans = MAX( ans , dp[v][m][] );
if( m > ) ans = MAX( ans , dp[v][m][] );
printf("%d\n",ans);
}
return ;
}