ACM DP Max Sum Plus Plus

我会带着你远行 2022-06-11 03:54 144阅读 0赞

滴，集训第十三天打卡。

今天依旧是DP专题，但是下午去玲珑杯划了会水，还打铁了...

委屈，感觉还是DP比较亲热。

**HDU 1024 Max Sum Plus Plus**

**![20170729183109292][]**

题目大意：找N段，长度为M，输入M个数，使得和最大。（最大m段子段和）

思路：dp\[i\]\[j\]表示前j个数分成i组的最大值

动态转移方程：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<string.h>
    int a[1000005],now[1000005],pre[1000005];
    using namespace std;
    int main()//A
    {
        int n,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=-999999999;
                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;
                    if(now[j]>maxx)
                    maxx=now[j];
                }
            }
            printf("%d\n",maxx);
        }
        return 0;
    }

[20170729183109292]: /images/20220611/1c36d0982fca443eb0ba75abe3bd66e6.png

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关 C plus plus 是什么

C++ 是一种高级程序设计语言，它是在 C 语言的基础上发展而来的，具有更强的程序封装和面向对象的特性。C++ 是一种通用的、静态的、强类型的编程语言，它支持过程化编程，也支持

Love The Way You Lie/ 2024年03月25日 19:48/ 0 赞/ 37 阅读

相关 hdu 1003 Max Sum （dp）

Max Sum Problem Description Given a sequence a\[1\],a\[2\],a\[3\]......a\[n\],

快来打我*/ 2024年02月17日 20:50/ 0 赞/ 19 阅读

相关 [kuangbin带你飞]专题十二基础DP1 A - Max Sum Plus Plus HDU - 1024

A - Max Sum Plus Plus HDU - 1024 题目链接：[https://vjudge.net/contest/68966\problem/A

我会带着你远行/ 2023年08月17日 15:41/ 0 赞/ 109 阅读

相关 MODBUS PLUS测试软件,Modbus Plus

产品概览 Modbus Plus 设备驱动与 KEPServerEX 协同工作，在 OPC 客户端和使用 Modbus Plus 协议的 PLC 之间提供数据交换。KEPSe

ゝ一世哀愁。/ 2022年09月01日 15:57/ 0 赞/ 173 阅读

相关 HDU--Max Sum

Max Sum Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/O

小咪咪/ 2022年08月26日 05:52/ 0 赞/ 24 阅读

相关 HDOJ 1003-Max Sum【DP】

Max Sum Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Othe

我会带着你远行/ 2022年08月20日 04:19/ 0 赞/ 23 阅读

相关 Max Sum

Max Sum Time Limit: 2000ms Memory limit: 32768K 有疑问？点这里^\_^ 题目描述 Given a se

拼搏现实的明天。/ 2022年08月18日 02:30/ 0 赞/ 156 阅读

相关 ACM DP Max Sum Plus Plus

滴，集训第十三天打卡。今天依旧是DP专题，但是下午去玲珑杯划了会水，还打铁了... 委屈，感觉还是DP比较亲热。 HDU 1024 Max Sum Plus Plus

我会带着你远行/ 2022年06月11日 03:54/ 0 赞/ 145 阅读

相关 A - Max Sum Plus Plus HDU - 1024——基础dp

Think: 1知识点：基础dp 2题意：n个数分成m部分的最大值二维表示 dp[i][j]:j个数分成i部分的最大值状态转移方程 dp

ゝ一世哀愁。/ 2022年06月10日 01:13/ 0 赞/ 147 阅读

相关 HDU-1003 Max Sum（dp）

Problem Description: Given a sequence a\[1\],a\[2\],a\[3\]......a\[n\], your job is to

阳光穿透心脏的1/2处/ 2022年04月24日 02:34/ 0 赞/ 134 阅读