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

ゝ一世哀愁。 2022-06-10 01:13 136阅读 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 条评论，136人围观）

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

相关阅读

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

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

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

相关【HDU】1402 A * B Problem Plus 【FFT】

传送门：【HDU】1402 A \ B Problem Plus 题目分析：这就是大数乘法题，问两个大数相乘的结果，由于O(n2)的算法复杂度太大，所以我们用FFT来优化

缺乏、安全感/ 2022年08月05日 04:28/ 0 赞/ 141 阅读

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

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

相关 ACM DP Max Sum Plus Plus

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

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

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

相关 hdu--1003--Max Sum

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

向右看齐/ 2022年05月26日 01:29/ 0 赞/ 110 阅读

相关 hdu 1003 Max Sum

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

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