hdu 1024 Max Sum Plus Plus(最大m子段和)

1.

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int INF=1<<30;
int a[1000005];
int dp[1000005];
int maxx[1000005];

int main()
{
    int m,n;
    while(scanf("%d%d",&m,&n)==2)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            dp[i]=0;
            maxx[i]=0;
        }
        dp[0]=0;
        maxx[0]=0;
        int ans;
        for(int i=1;i<=m;i++)
        {
            ans=-INF;
            for(int j=i;j<=n;j++)
            {
                dp[j]=max(dp[j-1],maxx[j-1])+a[j];
                maxx[j-1]=ans;
                ans=max(ans,dp[j]);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
时间: 05-13

hdu 1024 Max Sum Plus Plus(最大m子段和)的相关文章

HDU 1024 Max Sum Plus Plus --- dp+滚动数组

HDU 1024 题目大意:给定m和n以及n个数,求n个数的m个连续子系列的最大值,要求子序列不想交. 解题思路:<1>动态规划,定义状态dp[i][j]表示序列前j个数的i段子序列的值,其中第i个子序列包括a[j], 则max(dp[m][k]),m<=k<=n 即为所求的结果 <2>初始状态: dp[i][0] = 0, dp[0][j] = 0; <3>状态转移: 决策:a[j]自己成为一个子段,还是接在前面一个子段的后面 方程: a[j]直接接在前面

[2016-03-28][HDU][1024][Max Sum Plus Plus]

时间:2016-03-28 17:45:33 星期一 题目编号:[2016-03-28][HDU][1024][Max Sum Plus Plus] 题目大意:从n个数字提取出一定数字组成m个部分,使得这个部分的总和最大 分析: dp[i][j]表示前i段计算第j个数字,dp[i][j] = max(dp[i - 1][j - 1] + a[j],dp[i][k] + a[j]); #include <algorithm> #include <cstring> #include &

Hdu 1024 Max Sum Plus Plus (dp)

题目链接: Hdu 1024 Max Sum Plus Plus 题目描述: 给出n个数,问m段连续子序列的和相加最大是多少? 解题思路: dp[i][j]表示把前i个元素(包括第i个),分成j段的最大和.状态转移方程就是dp[i][j] = max (dp[i-1][j] + arr[j],  max( dp[k][j-1]) + arr[j]),其中0<k<i.(第i个元素是保存在第j段,还是自己单独成段) 由于1<=n<=1000,000.n*n的数组肯定会爆炸,所以要对方程

hdu 1024 Max Sum Plus Plus(DP)

转移方程dp[i][j]=Max(dp[i][j-1]+a[j],max(dp[i-1][k] ) + a[j] ) 0<k<j 此链接中有详解点击打开链接 #include<stdio.h> #include<algorithm> #include<iostream> using namespace std; #define MAXN 1000000 #define INF 0x7fffffff int dp[MAXN+10]; int mmax[MAXN

HDU 1024 Max Sum Plus Plus

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1024 Max Sum Plus Plus Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 21926    Accepted Submission(s): 7342 Problem Description Now I think you ha

HDU 1024 Max Sum Plus Plus【动态规划求最大M子段和详解 】

Max Sum Plus Plus Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 29942    Accepted Submission(s): 10516 Problem Description Now I think you have got an AC in Ignatius.L's "Max Sum" problem

HDU 1024 Max Sum Plus Plus(二维数组转化为一维数组)

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 seq

hdu 1024 Max Sum Plus Plus (子段和最大问题)

Max Sum Plus Plus Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17336    Accepted Submission(s): 5701 Problem Description Now I think you have got an AC in Ignatius.L's "Max Sum" problem

hdu 1024 Max Sum Plus Plus(简单dp)

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1024 题意:给定一个数组,求其分成m个不相交子段和的最大值. 这题有点问题其实m挺小的但题目并没有给出. dp[i][j]表示取第i 位的数共取了j段然后转移方程显然为 dp[i][j]=max(dp[i - 1][j]+a[j] , max(dp[j - 1][j - 1]~dp[i - 1][j - 1]))(大致意思是取第i位要么i-1位取了j个那么a[j]刚好能与i-1拼成一段,或者j -