HDU 1024 Max Sum Plus Plus

http://acm.hdu.edu.cn/showproblem.php?pid=1024

题意:可不连续的m个子段的最大和

分析:首先由于n很大,所以需要运用滚动数组,其次单个值也不小所以得考虑int64           接下来就是动态规划的思路了,这道题想了大概一上午没什么好思路,只想到第j个数要不属于第i组,要不独自成组           所以我只想到的转移方程为dp[i,j]=max(dp[i-1,j-1],dp[i][j-1])+num[j]           其中dp[i,j]为j个数分成i组的时候其最大和是多少                 dp[i-1,j-1]表示第j个数独自成组                 dp[i,j-1]表示第j个数合到前一个数           这个思路只对了一半,错在当j要独自成组的时候,并不一定dp[i-1,j-1]就是最大值,还有可能j-1这个数没有要,              dp[i-1,j-2] 或者dp[i-1,j-3]是最大的           根据这个,我又重新找出dp[i-1,k](i-1<=k<j)中的最大值,但是此时的dp循环是三个for循环了,果断超时。           后来看了别人代码,才了解定义一个MAX,一直记录着对于当前i的某个j的最大dp[i-1,k],由于对于j来说,必定从i开始循环过来的,所以MAX就是记录以前的最大值。

          然后还要注意的是,循环当前i的时候,需要剩下m-i个数的,让后面的人能够有数可用

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MN=1000010;
const int INF=999999999;
#define LL long long
//dp[i,j]表示i个组里有j物品的最大和
LL dp[2][MN];
int num[MN];

int main()
{
    int i,j,n,m,k;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            dp[0][i]=dp[1][i]=0;
            scanf("%d",&num[i]);
        }
        dp[0][0]=dp[1][0]=0;
        int t=1;
        for(i=1;i<=m;i++)
        {
            dp[t][i]=dp[1-t][i-1]+num[i];
            LL MAX=dp[1-t][i-1];
            for(j=i+1;j<=n-(m-i);j++)
            {
                MAX=max(MAX,dp[1-t][j-1]);
                dp[t][j]=max(MAX,dp[t][j-1])+num[j];
            }
            t=1-t;
        }
        t=1-t;
        LL MAX=-INF;
        for(i=m;i<=n;i++)
        {
            if(MAX<dp[t][i]) MAX=dp[t][i];
        }
        printf("%I64d\n",MAX);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据架构

UML(一) 类图详解

39960
来自专栏计算机视觉与深度学习基础

Leetcode 164 Maximum Gap 桶排序好题

Given an unsorted array, find the maximum difference between the successive ele...

22750
来自专栏Fish

CUDA PTX ISA阅读笔记(二)

8. 第八章 指令集 这一章占了整个手册的一大半(百十来页吧),主要介绍各种指令,虽然页数很多,但是大多数指令都很简单。 8.1. 指令的形式和语义描述 这章就...

60350
来自专栏数据处理

mat(矩阵)与array(数组)区别

35630
来自专栏数据结构与算法

2729:Blah数集

2729:Blah数集 查看 提交 统计 提问 总时间限制:3000ms内存限制:65536kB描述大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah,对...

34640
来自专栏和蔼的张星的图像处理专栏

162. 矩阵归零先找为零的位置,再分别置零

给定一个m×n矩阵,如果一个元素是0,则将其所在行和列全部元素变成0。 需要在原矩阵上完成操作。

17710
来自专栏mathor

TRIE(3)

 搜索引擎现在一般都有关键词提示或者说是补全功能。就是当你在搜索框里输入一个关键词s时,搜索引擎会自动提示你一些频率比较高,同时前缀是s的关键词  这道...

11220
来自专栏QQ音乐技术团队的专栏

Android Native 开发之 NewString 与 NewStringUtf 解析

本文将从一个 Native Crash 分析入手,带大家了解我们平时开发中,那些容易忽略但又很值得学习的底层源码知识。

1.6K90
来自专栏owent

POJ PKU 2549 Sumsets 解题报告

题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=2549

10310
来自专栏云霄雨霁

关系代数

21600

扫码关注云+社区

领取腾讯云代金券