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

我会带着你远行 2023-08-17 15:41 108阅读 0赞

## A - Max Sum Plus Plus ##

#  HDU - 1024 #

题目链接：[https://vjudge.net/contest/68966\#problem/A][https_vjudge.net_contest_68966_problem_A]

题目：

现在我觉得你在Ignatius.L的“Max Sum”问题上得到了一个AC。要成为一个勇敢的ACMer，我们总是挑战自己更难的问题。现在你面临着一个更加困难的问题。  
  
    给定连续的数字序列S 1，S 2，S 3，S 4 ... S x，... S n（1≤x≤n≤1,000,000，-32768≤Sx≤32767）。我们定义函数sum（i，j）= S i + ... + S j（1≤i≤j≤n）。  
  
    现在给出一个整数m（m> 0），你的任务是找到m对i和j，它们使得和（i 1，j 1）+ sum（i 2，j 2）+ sum（i 3，j 3） + ... + sum（im，jm）maximal（不允许ix≤iy≤jx或ix≤jy≤jx）。  
  
    但我很懒，我不想写一个特殊判断模块，所以你不必输出m对i和j，只输出和的最大总和（ix，jx）（1≤x ≤m）相反。 ^ \_ ^  
输入  
    每个测试用例将以两个整数m和n开始，接着是n个整数S 1，S 2，S 3 ... S n。  
    处理到文件结尾。  
产量  
    在一行中输出上述最大总和。  
样本输入  
  
    1 3 1 2 3  
    2 6 -1 4 -2 3 -2 3  
  
样本输出  
  
    6  
    8

思路：借用其他博客的两张图：

![1705372-20190804142906553-1954038354.png][]

比如：dp\[2\]\[4\]=max(max(-1,4,2,) , 2)+num\[4\]=7；

![1705372-20190804142919249-475135153.png][]

//
    // Created by hy on 2019/8/4.
    //
    #include <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <set>
    #include<math.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e6+10;
    int dp[maxn],frontmax[maxn],num[maxn];
    #define MAX 0x3f3f3f3f
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&m,&n))
        {
            for(int i=1;i<=n;i++)
                scanf("%d",&num[i]);
            memset(dp,0,sizeof(dp));
            memset(frontmax,0,sizeof(frontmax));
            int temp;
            for(int i=1;i<=m;i++)
            {
                temp=MAX*(-1);
                for(int j=i;j<=n;j++)
                {
                    dp[j]=max(frontmax[j-1],dp[j-1])+num[j];//dp[j]存j之前最大的和，frontmax存j-1之前最大的值
                    frontmax[j-1]=temp;
                    temp=max(temp,dp[j]);//temp值不断更新为最大的
                }
            }
            printf("%d\n",temp);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11298163.html

[https_vjudge.net_contest_68966_problem_A]: https://vjudge.net/contest/68966#problem/A
[1705372-20190804142906553-1954038354.png]: /images/20230810/bc4df8a192c1410eab34847200c9d151.png
[1705372-20190804142919249-475135153.png]: /images/20230810/68aeda48c70a414c91defeb4ffc0248a.png