先来题
Max Sum Plus Plus
| 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 ≤ 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. ^_^ |
Input
| Each 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. |
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. |
这道题，就是求M段最大子序列和，我对这稍微有一点理解，不知道错不，如果有错，希望大佬能够指教
//https://cn.vjudge.net/contest/177074#problem/A#include<cstdio>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<cstring>
#include<map>
#include<stack>
using namespace std;
#define inf 0x3f3f3f3f
#define LL long long
int dp[2][1000005];
int a[1000005];
int main()
{int n,m;while(cin>>m>>n){for(int i=1;i<=n;i++){cin>>a[i];}memset(dp,0,sizeof(dp));int maxx;for(int i=1;i<=m;i++){ maxx=-inf;for(int j=i;j<=n;j++){dp[1][j]=max(dp[1][j-1],dp[0][j-1])+a[j];dp[0][j-1]=maxx;if(dp[1][j]>maxx) maxx=dp[1][j];}}cout<<maxx<<endl;}return 0;
}| 这个算法是很经典求最大M子序列了，最重要的就是DP那一段，我对于那一段的理解就是：↓↓↓↓↓ 在n==1的时候这个DP就像求一段的最大连续子序列一样，dp中存下的就是写的SUM（也就是一直加a[i]然后与0比较的那个数，当成n==2时，要找最大的两段，这时候那个DP[0][ J - 1]相当于那个一直比较的0，然后和那个类似，我感觉就是这样，感觉还是不算太理解，也感觉自己理解的有很多问题，我没有找到解释dp是什么的博客，如果大佬有相关的博客，欢迎留言。 |
先留下一个解释挺详细的大佬博客（由于自己太菜，还是没看懂) : 传送门