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

ゝ一世哀愁。 2022-06-10 01:13 146阅读 0赞

Think:  
1知识点：基础dp  
2题意：n个数分成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

一维优化

dp[j]数组表示前j个数分成当前i部分的最大值
    mav[j]数组表示第j层的最大值
    状态转移方程
    dp[j] = max(dp[j-1]+a[j], mav[j-1]+a[j]);

[vjudge题目链接][vjudge]

[建议参考博客1][1]  
[建议参考博客2][2]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 1e6 + 4e2;
    
    int dp[N], a[N], mav[N];
    /*1.dp[j]数组表示前j个数分成当前i部分的最大值*/
    /*2.mav[j]数组表示第j层的最大值*/
    
    int main(){
        int m, n, i, j, mx;
        while(~scanf("%d %d", &m, &n)){
            for(i = 1; i <= n; i++)
                scanf("%d", &a[i]);
            dp[0] = 0;
            memset(mav, 0, sizeof(mav));
            for(i = 1; i <= m; i++){
                mx = -inf;
                for(j = i; j <= n; j++){
                    dp[j] = max(dp[j-1]+a[j], mav[j-1]+a[j]);
                    mav[j-1] = mx;
                    mx = max(mx, dp[j]);/*更新记录分成i部分第j层的最大值*/
                }
            }
            printf("%d\n", mx);/*输出分成m部分的最大值*/
        }
        return 0;
    }

[vjudge]: https://vjudge.net/contest/163018#problem/A
[1]: http://blog.csdn.net/to_be_better/article/details/50557224
[2]: http://www.cnblogs.com/kuangbin/archive/2011/08/04/2127085.html

发表评论取消回复

表情：

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

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

相关阅读

相关 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 阅读

相关 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 阅读

相关 HDU 1402——A * B Problem Plus

题意：给定a，b，求a\b。思路： a,b的长度都为50000，直接模拟计算n\m肯定超时，可以用快速傅里叶变化计算，然后再把相应的系数化简出来。 code：

灰太狼/ 2022年07月19日 02:30/ 0 赞/ 109 阅读

相关 hdu1003: Max Sum

地址 [http://acm.hdu.edu.cn/showproblem.php?pid=1003][http_acm.hdu.edu.cn_showproblem.p

布满荆棘的人生/ 2022年07月14日 09:22/ 0 赞/ 158 阅读

相关 hdu 1003 Max Sum

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

╰+攻爆jí腚メ/ 2022年06月15日 05:59/ 0 赞/ 150 阅读

相关 ACM DP Max Sum Plus Plus

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

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

相关 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 阅读

相关 hdu 1003 Max Sum

hdu 1003 Max Sum 题意题解源代码 [传送门][Link 1] 题意现在有一个序列，求解序列的最长连续子序列的和，

你的名字/ 2021年10月13日 02:02/ 0 赞/ 312 阅读