HDU 1024 Max Sum Plus Plus

作者: ffacs 分类: 题目 发布时间: 2019-12-31 03:42

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

Problem Description

Input

Each test case will begin with two integers m and n, followed by n integers S1, S2, S3 ... Sn. Process to the end of file.

Output

Output the maximal summation described above in one line.

Solution

做了好久,果然算法竞赛笨是原罪。考虑状态转移方程 \(dp[j][i]=max(dp[j-1][i],mx[i-1])+a[j]\),意思就是在第\(j+1\)个位置之前有选了\(i\)段的和的最大值,并且\(j\)被选中。为什么要一定要有\(j\)呢?因为这样更方便状态转移。状态转移方程中的mx是指前j个元素中选了\(i\)段的和的最大值.

那么这个状态转移方程的意思就是,最后一个是\(a[j]\)\(i\)段的和的最大值,要么是\(a[j-1]\)是最后一个元素的有i段和的最大值(就是j不新增一段,和\(j-1\)连在一起)。要么是前面有\(i-1\)段了,我j新开一段得到的最大值的和。然后要注意一下初始化的问题。\(mx\)\(dp\)都应该要初始化成\(-INF\)。因为数据是有负数的.

#include<bits/stdc++.h>
#define rg register
#define il inline
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
ll read(){
    ll ans = 0,flag = 1; char ch;
    while((ch=getchar())<'0'||ch>'9') if(ch =='-') flag=-1;ans = ch ^ 48;
    while((ch=getchar())>='0'&&ch<='9') ans=(ans<<3)+(ans<<1)+(ch^48);
    return flag*ans;
}
void WRI(ll x){if(x<0){ putchar('-');x=-x; }if(x>9) WRI(x/10);putchar(x%10+'0');}
void write(int x,char o){ WRI(x),putchar(o); }
ll dp[10005];
ll mx[10005];
ll a[1000005];
int main(){
    int m,n;
    while(cin>>m>>n){
        for(rg int i=0;i<n;i++) a[i]=read();
        for(rg int i=1;i<=m;i++)
            dp[i]=mx[i]=-1e12;
        for(rg int i=0;i<n;i++){
            for(rg int j=m;j>=1;j--){
                dp[j]=max(mx[j-1],dp[j])+a[i];
                mx[j]=max(dp[j],mx[j]);
            }
        }
        cout<<mx[m]<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注