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吃自助餐
更多推荐
【最大m子段和】hdu 1024
发布评论