题目大意:
Max Sum Plus Plus
给你m个数,在其中选取n组
使得每组的数连续,且互相不能相交,
求出最大的各组数的和
思路:
采取二维dp的方法
d p [ i ] [ j ] 中,i 为组数,j为以a [ j ] 结尾
状态转移方程为
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] + a [ j ] , d p [ i − 1 ] [ k ] + a [ j ] ) ( 0 < k < j )
因为复杂度为O ( n2 ),所以我们可以采取将二维dp变成一维dp,将其中的d p [ i − 1 ] [ k ] 用一个单独的一维数组表示
AC Code:
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define INF 1<<30
const int N=1e6 +9;
int n, m;
int dp[N], f[N], a[N];
int main(){
while(scanf("%d%d", &n, &m)!=EOF){
memset(dp, 0, sizeof(dp));
memset(f, 0, sizeof(f));
for(int i=1; i<=m; i++) scanf("%d", &a[i]);
int mx=-INF;
//
for(int i=1; i<=n; i++){
mx=-INF;
for(int j=i; j<=m; j++){
dp[j]=max(dp[j-1], f[j-1])+a[j];
f[j-1]=mx;
mx=max(dp[j], mx);
}
}
printf("%d\n", mx);
}
return 0;
}
Comments | NOTHING