題干：

?

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

Hint

Huge input, scanf and dynamic programming is recommended.

?

解題報告：

? ?dp[i][j] ?i個子段，并且以第j個數字結尾 ?的最大和，然后優化掉一維。復雜度O(n*m)

AC代碼：

#include<bits/stdc++.h> #define ll long long using namespace std;const int MAX = 100005; const ll INF = 922337203685477580; ll num[MAX] ,dp[MAX] ,mk[MAX]; int main () {int n,m;ll maxx;while(~scanf("%d%d",&m,&n)) {for(int i = 1 ; i <= n ; i++) scanf("%lld",&num[i]);memset(dp,0,sizeof(dp));memset(mk,0,sizeof(mk));for(int i = 1 ; i <= m ; i ++) {maxx = -INF;for(int j = i ; j <= n ; j ++) {if(i == j) dp[j] = mk[j-1] + num[j];else dp[j] = max(dp[j-1] ,mk[j-1]) + num[j];mk[j-1] = maxx;maxx = max(maxx,dp[j]);}}printf("%lld\n",maxx);}return 0; }

TLE代碼：（復雜度O(m* n^2)）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; ll dp[505][505]; ll a[MAX]; //dp[i][j] i個子段，并且以第j個數字結尾 的最大和 int main() {int n,m;while(cin>>m>>n) {for(int i = 1; i<=n; i++) scanf("%lld",a+i);memset(dp,0,sizeof dp);for(int i = 1; i<=m; i++) {for(int j = 1; j<=n; j++) {dp[i][j] = dp[i][j-1] + a[j]; if(j<=i) continue;for(int k = 1; k<j; k++) {dp[i][j] = max(dp[i][j],dp[i-1][k] + a[j]);}}}ll ans = -99999999999;for(int i = 1; i<=n; i++) ans = max(ans,dp[m][i]);cout <<ans <<endl;}return 0 ; }

優化一層循環：（但是空間上過不去。。。）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; ll dp[505][505]; ll pre[505][505]; ll a[MAX]; //dp[i][j] i個子段，并且以第j個數字結尾 的最大和 int main() {int n,m;while(~scanf("%d%d",&m,&n)) {for(int i = 1; i<=n; i++) scanf("%lld",a+i);memset(dp,0,sizeof dp);memset(pre,0,sizeof pre);for(int i = 1; i<=m; i++) {for(int j = 1; j<=n; j++) {dp[i][j] = dp[i][j-1] + a[j]; if(j<=i) continue;dp[i][j] = max(dp[i][j],pre[i-1][j-1] + a[j]);pre[i][j] = max(pre[i][j-1],dp[i][j]);}}ll ans = -99999999999;for(int i = 1; i<=n; i++) ans = max(ans,dp[m][i]);printf("%lld\n",ans);}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【HDU - 1024 】Max Sum Plus Plus （dp及优化，最大m子段和）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。