hdu1003 1024 Max Sum&Max Sum Plus Plus【基础dp】

时间：2022-02-24 15:55:12

转载请注明出处，谢谢：http://www.cnblogs.com/KirisameMarisa/p/4302208.html   ---by 墨染之樱花

dp是竞赛中常见的问题，也是我的弱项orz，更要多加练习。看到邝巨巨的dp专题练习第一道是Max Sum Plus Plus，所以我顺便把之前做过的hdu1003 Max Sum拿出来又做了一遍

HDU 1003 Max Sum

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1003

题目描述：给一个整数序列，求其中的一段连续子序列，使它的和最大值以及这个序列的起始下标

思路：简单的dp，抓住“连续”来入手。构造pair<int,int> dp[i]为以a[i]结尾的连续子序列的最大和以及这段子序列的起点，那么很简单就能得出dp[i].first=max(dp[i-1].first+a[i],a[i])，因为以a[i]结尾只有两种情况：1、粘在以a[i-1]结尾的子序列后面，那么最大和就是前面的最大和加上a[i]，起点则就是前面的起点；2、a[i]自成一个新序列，那么最大和就是它自己，起点也是它自己，比较一下那种情况更大就行了。

另外由于dp[i]只与dp[i-1]有关，所以其实只需要重复利用一个变量就行了，这里写成数组看得明白一点

代码：

#include <iostream>

#include <ios>

#include <iomanip>

#include <functional>

#include <algorithm>

#include <vector>

#include <sstream>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <string>

#include <set>

#include <map>

#include <cstdio>

#include <cstdlib>

#include <cctype>

#include <cmath>

#include <cstring>

#include <climits>

using namespace std;

#define XINF INT_MAX

#define INF 1<<30

#define MAXN 100000+10

#define eps 1e-10

#define zero(a) fabs(a)<eps

#define sqr(a) ((a)*(a))

#define MP(X,Y) make_pair(X,Y)

#define PB(X) push_back(X)

#define PF(X) push_front(X)

#define REP(X,N) for(int X=0;X<N;X++)

#define REP2(X,L,R) for(int X=L;X<=R;X++)

#define DEP(X,R,L) for(int X=R;X>=L;X--)

#define CLR(A,X) memset(A,X,sizeof(A))

#define IT iterator

#define PI  acos(-1.0)

#define test puts("OK");

#define _ ios_base::sync_with_stdio(0);cin.tie(0);

typedef long long ll;

typedef pair<int,int> PII;

typedef priority_queue<int,vector<int>,greater<int> > PQI;

typedef vector<PII> VII;

typedef vector<int> VI;

#define X first

#define Y second

PII dp[MAXN];

int num[MAXN];

int main()

{_

    int T;

    scanf("%d",&T);

    REP(k,T)

    {

        int n;

        CLR(dp,);

        scanf("%d",&n);

        REP(i,n)

            scanf("%d",&num[i]);

        dp[]=MP(num[],);

        for(int i=;i<n;i++)

        {

            if(dp[i-].X+num[i]>=num[i])

            {

                dp[i].X=dp[i-].X+num[i];

                dp[i].Y=dp[i-].Y;

            }

            else

            {

                dp[i].X=num[i];

                dp[i].Y=i;

            }

        }

        int Max=-INF,ans1=,ans2=;

        REP(i,n)

        {

            if(dp[i].X>Max)

            {

                Max=dp[i].X;

                ans1=dp[i].Y+;

                ans2=i+;

            }

        }

        printf("Case %d:\n",k+);

        printf("%d %d %d\n",Max,ans1,ans2);

        if(k<T-)

            printf("\n");

    }

    return ;

}

HDU 1024 Max Sum Plus Plus

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1024

题目描述：与1003差不多，这里另外给了m，求的是则是m段互不相交的连续子序列的最大和。比如序列为-1 4 -2 3 -2 3，m=2时，最大值就是8（4和3,-2,3两段）

思路：构造dp[i][j]为以a[i]结尾的j段子序列的最大和，当然j=1时其实就是上面一题。状态转移方程也差不多：1、粘在以a[i-1]结尾的j段子序列后面，那么dp[i][j]=dp[i-1][j]+a[i]，2、自成一段新序列，此时要注意的是由于几段序列之间可以分开，所以并不是简单的dp[i-1][j-1]+a[i]，而是在max(dp[i-1][j-1],dp[i-2][j-1],...,dp[j-1][j-1])+a[i]。由于n的范围比较大，二维数组开不下，而好在dp的第i层只与第i-1层有关，可以重复利用一维数组。另外情况2中需要一次次地找max，会超时，可以看到dp[i][j]一定比上一层的大，所以可以用数组posMax来记录这个位置曾经出现过的最大的数，下一层就可以直接使用节省时间。

时间复杂度是o(nm)，奇怪的是题中并没有给m的范围，这样都能AC看来数据都是比较小的（-_-b汗）

#include <iostream>

#include <ios>

#include <iomanip>

#include <functional>

#include <algorithm>

#include <vector>

#include <sstream>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <string>

#include <set>

#include <map>

#include <cstdio>

#include <cstdlib>

#include <cctype>

#include <cmath>

#include <cstring>

#include <climits>

using namespace std;

#define XINF INT_MAX

#define INF 0x7fffffff

#define MAXN 1000000+10

#define eps 1e-8

#define zero(a) fabs(a)<eps

#define sqr(a) ((a)*(a))

#define MP(X,Y) make_pair(X,Y)

#define PB(X) push_back(X)

#define PF(X) push_front(X)

#define REP(X,N) for(int X=0;X<N;X++)

#define REP2(X,L,R) for(int X=L;X<=R;X++)

#define DEP(X,R,L) for(int X=R;X>=L;X--)

#define CLR(A,X) memset(A,X,sizeof(A))

#define IT iterator

#define PI  acos(-1.0)

#define test puts("OK");

#define _ ios_base::sync_with_stdio(0);cin.tie(0);

typedef long long ll;

typedef pair<int,int> PII;

typedef priority_queue<int,vector<int>,greater<int> > PQI;

typedef vector<PII> VII;

typedef vector<int> VI;

#define X first

#define Y second

int a[MAXN];

int dp[MAXN];

int posMax[MAXN];

inline int _max(int x,int y)

{

    return x>y?x:y;

}

int main()

{_

    //freopen("out.txt","w",stdout);

    int m,n;

    while(~scanf("%d%d",&m,&n))

    {

        for(int i=;i<=n;i++)

        {

            scanf("%d",&a[i]);

            posMax[i]=-INF;

            dp[i]=-INF;

        }

        int ans=-INF;

        for(int i=;i<=n;i++)

        {

            int t=min(i,m);

            for(int j=;j<=t;j++)    //j不能比i大，而j>m时又没有意义，所以只要循环到min(i,m)

            {

                dp[j]=_max(dp[j],posMax[j-])+a[i];

                if(j==m)

                    ans=_max(ans,dp[j]);

            }

            for(int j=;j<=t;j++)

                posMax[j]=_max(posMax[j],dp[j]);

            /*

            printf("dp:");

            for(int j=1;j<=t;j++)

                printf("\t%d",dp[j]);

            printf("\npM:");

            for(int j=1;j<=t;j++)

                printf("\t%d",posMax[j]);

            printf("\n\n");

            */

        }

        printf("%d\n",ans);

    }

    return ;

}

/*

3 10 -3 5 6 -4 0 1 3 -2 10 1

输出：26

4 15 1 -6 0 4 -9 -8 7 8 0 -1 3 -8 2 5 1

输出：30

*/

相关文章