动态规划题 HDU-1024

http://acm.hdu.edu.cn/showproblem.php?pid=1024

Now I think you have got an AC in Ignatius.L's "Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem. 

Given a consecutive number sequence S 1, S 2, S 3, S 4 ... S x, ... S n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S x ≤ 32767). We define a function sum(i, j) = S i + ... + S j (1 ≤ i ≤ j ≤ n). 

Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i 1, j 1) + sum(i 2, j 2) + sum(i 3, j 3) + ... + sum(i m, j m) maximal (i x ≤ i y ≤ j x or i x ≤ j y ≤ j x is not allowed). 

But I`m lazy, I don't want to write a special-judge module, so you don't have to output m pairs of i and j, just output the maximal summation of sum(i x, j x)(1 ≤ x ≤ m) instead. ^_^

题意就是求你n个数字m段和的最大值

用动态规划求dp[n][m] 表示用前m个数划分为n块的最大和

转移方程为 dp[n][m]=max(dp[n][m-1]+a[m],max(dp[n-1][t])+a[m]),其中dp[n][m-1]+a[m]表示第m个在前i块中后面表示的是在自己独立变成一个块（1<=t<=m-1）

那么问题来了如果用这种方法复杂度为（n^3）因此我们要化简一下，求max(dp[n-1][t])的时候重复求了一些过程，因此只需要改成设一个变量M 表示前1到m-1的最大值 M=max(M,dp[i-1][j-1]);

但是空间上不够，因此用一个滚动数组 dp[2][MAN]；在求M的用到了i-1;

完整代码：

#include <stdlib.h>

#include<iostream>

#include<algorithm>

//#include<bits/stdc++.h>

#include<cstdio>

#include<cstring>

#include<cmath>

#define ll long long

const ll INF=0x3f3f3f3f;

#define mod 1000000007

#define mem(a,b) memset(a,b,sizeof(a))

//__builtin_popcount

using namespace std;

//priority_queue

const ll MAX=1000000;

int Max[MAX+10];

int dp[2][MAX+10];

int a[MAX+10];

int main()

{

    int n,m;

    while(cin>>m>>n)

    {

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

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

        mem(Max,0);

        mem(dp,0);

        int M;

        for(int i=1; i<=m; i++)

        {

            M=-0x3f3f3f3f;

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

            {

                M=max(M,dp[(i-1)%2][j-1]);

                if(i!=j)

                    dp[i%2][j]=max(dp[i%2][j-1]+a[j],M+a[j]);

                else dp[i%2][j]=M+a[j];

            }

        }

        M=-0x3f3f3f3f;

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

            M=max(M,dp[m%2][i]);

        cout<<M<<endl;

    }

}

巴特西

动态规划题 HDU-1024

最新文章

热门文章