hdu 1024 最大m段不相交线段和

[题目传送门](http://acm.hdu.edu.cn/showproblem.php?pid=1024)//res tp hdu

数据范围1e6，若是开二维会爆

考虑用滚动数组优化

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define rep(i,a,b) for(int i=(a);i<=(b);++i)

#define per(i,a,b) for(int i = (a);i>=(b);--i)

#define fo(i,a,b) for(int i =(a);i<(b);++i)

#define de(x) cout<<#x<<" = "<<x<<endl;

#define endl '\n'

#define ls(p) ((p)<<1)

#define rs(p) (((p)<<1)|1)

using namespace std;

typedef long long ll;

const int mn = 1e6+10;

// search m seg to make the sum of them max

//1e6, more than one test

ll arr[mn];

ll dp[mn],pre[mn];

// 滚动数组优化二维dp

int main(){

	int n,m;

	while(scanf("%d %d",&m,&n)!=EOF){

		rep(i,1,n) scanf("%lld",&arr[i]);

		//dp[i][j] = max(dp[i][j-1]+arr[j],max(dp[i-1][k])+arr[j]) (1 <=k<=j-1)

		ll MAX;

		rep(i,1,n) dp[i] = pre[i] = 0;

		rep(i,1,m){

			MAX = -1e9; // max in [1,j-1]

			rep(j,i,n){

				dp[j] = max(dp[j-1],pre[j-1])+arr[j];

				pre[j-1] = MAX;

				MAX = max(MAX,dp[j]);

			}

		}

		printf("%lld\n",MAX);

	}

}

巴特西

hdu 1024 最大m段不相交线段和

最新文章

热门文章