1、http://acm.hdu.edu.cn/showproblem.php?pid=1024
2、题目大意:
已知有n个数,求m段不相交的子段权值之和最大,
状态转移方程:dp[i][j]表示以i为结尾元素的j个子段的数和
dp[i][j]=max(dp[i-1][j]+a[i],dp[i-k][j-1]+a[i]);其中(j-1<=k<=n-m+1)
此题实现这种思想:
for(i=1;i<=m;i++)
{
maxx=(-1)*(N*90);//初始化
for(j=i;j<=n;j++)
{
now[j]=max(now[j-1]+a[j],pre[j-1]+a[j]);//其中now[j-1]表示的是以j-1结尾的元素i个子段的数和,pre[j-1]表示的是前j-1个元素中i-1个子段的数和
pre[j-1]=maxx;//放在此处是为了实现pre[j-1]+a[j]中a[j]是一个独立的子段,那么此时就应该用的是i-1段
if(now[j]>maxx)
{
maxx=now[j];
}
}
}
3、题目:
Max Sum Plus Plus
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11549 Accepted Submission(s): 3807
Problem Description
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 S1, S2, S3, S4... Sx, ... Sn(1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ Sx≤ 32767). We define
a function sum(i, j) = Si+ ... + Sj(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(i1, j1) + sum(i2, j2) + sum(i3, j3) + ... + sum(im,
jm) maximal (ix≤ iy≤ jxor ix≤ jy≤ jxis 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(ix, jx)(1 ≤ x ≤ m) instead. ^_^
Input
Each test case will begin with two integers m and n, followed by n integers S1, S2, S3... Sn.
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
4、代码:
-
#include<stdio.h>
-
#include<algorithm>
-
#include<string.h>
-
#defineN1000
-
inta[N+5];
-
intnow[N+5];
-
intpre[N+5];
-
usingnamespacestd;
-
intmain()
-
{
-
intn,m,maxx,i,j;
-
while(scanf("%d%d",&m,&n)!=EOF)
-
{
-
for(i=1;i<=n;i++)
-
scanf("%d",&a[i]);
-
memset(now,0,sizeof(now));
-
memset(pre,0,sizeof(pre));
-
for(i=1;i<=m;i++)
-
{
-
maxx=(-1)*(N*90);
-
for(j=i;j<=n;j++)
-
{
-
now[j]=max(now[j-1]+a[j],pre[j-1]+a[j]);
-
pre[j-1]=maxx;
-
if(now[j]>maxx)
-
{
-
maxx=now[j];
-
}
-
}
-
}
-
printf("%d\n",maxx);
-
}
-
return0;
-
}
分享到:
相关推荐
求一个最大子串和的加强版 任意多个字串之和最大 HDU 1024 max sum plus plus
杭电acm1297 #include<stdio.h> #include<string.h> #define m 1002 int f[m][70]={{1,1},{1,1},{1,2},{1,4}} void add(int p[],int q[],int sum[]) ...=10000){sum[i]-=10000 sum[i+1]++ } }
杭电ACMhdu1163
hdu1001解题报告
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
自己做的HDU ACM已经AC的题目
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
hdu题目分类