hdoj1024【DP.最 大 m 字 段 和】(写完我都怕。。。不忍直视。。)

弱弱上路,看了好多题解。。。。【A的】

题意就是求最大m子段和。

我们先用a[1e6+7]存入数据;

定义:DP[ i , j ] 为前 j 个元素的 i 个子段的最大和,且第 i 个子段中包含了元素 a[j]。

我们先来看:DP[ i , j ]状态方程由来;

对于一个元素 a[ j ] :

① 他可以自成一段;

②也可以包含第 i 段上,而且是第 i 段上的末尾元素;

那么:

对于①:DP[ i , j ]=max(DP[ i - 1 ,t ])+a[ j ]; t∈( i - 1 , j );

我把元素a[ j ]自成一段,我们的目的是要达到DP[ i , j ]最大,那么就是要使前面的 i - 1 段最大,所以需要找一下最大,而且第 i - 1 段中的末尾元素肯定是区间(i - 1 , j)上;

对于②:DP[ i , j ]=DP[ i , j - 1 ] + a[ j ];

其实一开始,我是不理解为什么就是DP[ i , j - 1 ]啊,为什么不可以是DP[ i , j - 2 ],DP[ i , j - 3 ],然后再举例子就真是自己sb了(T . T),因为前提是子段,是连续的!!然后现在我们的条件是元素a[ j ]在第 i 段上了,而且是该段上的最后一个元素;

那么就好了啊,已经搞好了;

=> DP[i,j]=max(max(DP[ i - 1 , t ] ) ,DP[ i , j - 1 ] )+a[ j ];

但是这样写,会发现。。。哇艹,他的n是1e6啊!!!你给我开个二维数组那样代表?这样是不行的;

我们可以看到DP[ i , j ] 的值只和 DP[ i , j - 1 ] 和DP[ i - 1 , t ] 这两个值相关,

因此不需要二维数组,可以用滚动数组,只需要两个一维数组,

用now[ j ] 表示现阶段的最大值,即 DP[ i , j − 1] + a[ j ]

用pre[ j ] 表示上阶段的最大值,即 max{DP[ i − 1,t ] )+ a[ j ]

代码:

#include<iostream>
#include<cstdio>
#include<math.h>
#include<queue>
#include<map>
#include<stdlib.h>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
const int N=1e6+7;
int a[N];
int pre[N];
int now[N];
int Max_duan(int m,int n)
{
int i,j,max_sum;
memset(pre,0,sizeof(pre));
memset(now,0,sizeof(now));
for(i=1;i<=m;i++){
max_sum=INT_MIN;
for(j=i;j<=n;j++){
now[j]=max(pre[j-1],now[j-1])+a[j];
pre[j-1]=max_sum;
if(max_sum<now[j])
max_sum=now[j];
}
pre[j-1]=max_sum;
}
return max_sum;
} int main()
{
int n,m;
while(~scanf("%d%d",&m,&n))
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("%d\n",Max_duan(m,n));
}
return 0;
}
上一篇:转:Oracle 数据泵详解


下一篇:Oracle数据泵详解