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(i2, j 2) + sum(i 3, j 3) + ... + sum(i m, j m) maximal (i x ≤ i y ≤ 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. ^_^
InputEach test case will begin with two integers m and n, followed by n integers S 1, S 2, S 3 ... S n.
Process to the end of file.
OutputOutput 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
N个数中去取M个互不相交的区间段,求最大的全体所要的区间段的和。
二维dp降成一维
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll inf = 4e18+10; const int mod = 1000000007; const int mx = 1e6; //check the limits, dummy typedef pair<int, int> pa; const double PI = acos(-1); ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } #define swa(a,b) a^=b^=a^=b #define re(i,a,b) for(int i=(a),_=(b);i<_;i++) #define rb(i,a,b) for(int i=(b),_=(a);i>=_;i--) #define clr(a) memset(a, 0, sizeof(a)) #define lowbit(x) ((x)&(x-1)) #define mkp make_pair void sc(int& x) { scanf("%d", &x); }void sc(int64_t& x) { scanf("%lld", &x); }void sc(double& x) { scanf("%lf", &x); }void sc(char& x) { scanf(" %c", &x); }void sc(char* x) { scanf("%s", x); } ll n, m; ll a[mx],d[mx],dp[mx][2],mxx[mx],ans; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while (~scanf("%lld%lld",&m,&n)){ ans = -inf; re(i, 0, n + 1)dp[i][0] = dp[i][1] = mxx[i] = 0; re(i, 1, n+1)sc(a[i]); re(j, 1, m + 1) { re(i, j, n + 1) { if (i == j)dp[i][j & 1] = dp[i - 1][(j - 1) & 1] + a[i]; else dp[i][j & 1] = max(dp[i - 1][j & 1] + a[i], mxx[i - 1] + a[i]); if (i - 1 == j)mxx[i - 1] = dp[i - 1][j & 1]; else mxx[i - 1] = max(mxx[i - 2], dp[i-1][j& 1]); } } re(i, m, n + 1)ans = max(ans, dp[i][m & 1]); printf("%lld\n", ans); } return 0; }