【最大m子段和】hdu 1024

hdu 1024"/>

【最大m子段和】hdu 1024

向那些认认真真写博客，将自己思考精髓记录并分享的人致敬ღ( ´･ᴗ･` )

参考博客1

参考博客2

参考博客3

队友博客

先看一下最大子段和问题

问题描述：N个整数组成的序列a[1],a[2],a[3],…,a[n]，找出一个连续序列，和是最大的。

状态定义：dp[i]以第i项为结尾的最大子段和

状态转移方程：若dp[i-1]>0,dp[i]=dp[i-1]+a[i]; 否则dp[i]=a[i];

最终答案为遍历1~n,找dp[i]的最大值，时间复杂度O(n)

再看一下最大子矩阵问题

问题描述：给定一个m*n的整数矩阵A，试求矩阵A的一个子矩阵，使其各个元素之和最大。

思路：取出两行i,j, 把这两行之间同一列的都加起来形成另外一个数组,求这个数组的最大子段和,求出来的这个和,就是这两行之间行数为j-i+1的子矩阵中最大的和，遍历所有的取法得到最大值（遍历i=1:n, j=i:n）

题意：最大子矩阵裸题

同样的题目，同样的代码，hdu 1081 wa了，还未查出原因，窒息（！！题目中明明说了一个矩阵，多样例读入就能A了mmd）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e2+10;
typedef long long LL;
const int INF=0x3f3f3f3f;
int a[N][N];
int n,m;
int main()
{memset(a,0,sizeof(a));cin>>n;for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){int tmp;cin>>tmp;a[i][j]=a[i-1][j]+tmp;           //存取前i行第j列的和}int maxx=-INF;for(int i=1;i<=n;++i){for(int j=i;j<=n;++j)            //求第i行到第j行之间宽为p-q+1的最大矩阵{int sum=0;                   //此处就是第i行到第j行每一列的值视作一维数组中的一个数字，进行最大子段和的计算for(int k=1;k<=n;++k){sum+=a[j][k]-a[i-1][k];if(sum<0) sum=0;if(sum>maxx) maxx=sum;}}}cout<<maxx<<endl;return 0;
}

最后看一下最大m子段和问题

问题描述：N个整数组成的序列a[1],a[2],a[3],…,a[n]，将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。

状态定义：为以第j个数为结尾的分为i段的和的最大值

状态转移方程：  将第j个数放入第j-1个数（因为一段必须是连续的，只能这样并入）

 将第j个数单独作为一段，由于i-1段至少需要i-1个数，所以范围要大于i-1

时间复杂度为O(m(n-m))

需要注意的事：根据题意确定初始化条件以及答案

如果要求必须选定m段，将答案初始化为数据个数*-INF，答案dp[m][m~n]中的最大值

如果可以选择不超过m的任意段，将答案初始化为0，答案为dp[i][j]中的最大值

hdu 1024

题意：最大m子段和裸题

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e6+10;
typedef long long LL;
const int INF=0x3f3f3f3f;
LL a[N];
LL dp[2][N];        //dp[i[j]代表前i个数组成j段的最大和int n,m;int main()
{while(scanf("%d%d",&m,&n)!=EOF){for(int i=1;i<=n;++i)scanf("%lld",&a[i]);for(int i=0;i<=n;++i){dp[0][i]=0;dp[1][i]=0;                 //输出要保证是整数}for(int i=1,k=1;i<=m;++i,k^=1){dp[k][i-1]=-INF;            //保证dp[i][i]一定被dp[i-1][i-1]更新,而不是被dp[i][i-1]更新LL maxx=-INF;for(int j=i;j<=n;++j){maxx=max(maxx,dp[k^1][j-1]);        //同步更新上一层的最小值dp[k][j]=max(dp[k][j-1],maxx)+a[j];}}LL ans=-(LL)N*INF;for(int i=m;i<=n;++i)ans=max(ans,dp[m&1][i]);cout<<ans<<endl;}return 0;
}

来记录一下自己对-2 11 -4 13 -5 6 -2分为1段最大值的理解

直接去想的话是最大子段和，按照最大m段和来想：分成0段是0

对于-2来说，左上方和左侧最大值为0，加上自己，是-2

对于11来说，左上方和左侧（-2）最大值是0，加上自己，是11

对于-4来说，左上方和左侧（11）最大值是11，加上自己，是7

以此类推

南邮wishare杯网络赛题面

AK选手柏老板的代码

南邮还是柏广凡同学最优秀（老板认证）

#include<bits/stdc++.h>
using namespace std;
#define N 100050
#define INF 0x3f3f3f3f
typedef long long LL;
LL n,m,dp[2][N],a[N],Max,ans,k=0;
int main(){scanf("%lld%lld",&n,&m);for (int i=1;i<=n;i++) scanf("%lld",&a[i]);for (int i=1;i<=m;i++){k=k^1;dp[k][i]=dp[k^1][i-1]+a[i];Max=dp[k^1][i-1];ans=dp[k][i];for (int j=i+1;j<=n;j++){Max=max(Max,dp[k^1][j-1]);dp[k][j]=max(max(Max+a[j],dp[k][j-1]+a[j]),0LL);ans=max(dp[k][j],ans);}}printf("%lld\n",ans);return 0;
}F：小Z吃自助餐