HDUMaxSumPlusPlus(二维dp）

link

题意：给你一个数组，有n个元素，选择m段两两没有没有交集的连续的段，输出这m段的和的最大值。

dp[ i ][ j ] 为 j 前面且包含 j 在内的数中选择 i 段的最大值，那么，dp[ i ][ j ] = max(dp[ i ][ j - 1] , dp[ i - 1 ][ k] ) + a[ j ] ,(k

注意的是dp[ i ] [ j ] (i > j)这种状态都是没有意义的，要赋值为-inf。

#include
#define ll long long
using namespace std;
const int maxn = 1e6+10,inf = INT_MAX;
int a[maxn];
int dp[maxn],pre[maxn];
int main()
{
int n,m;
while(~scanf("%d%d",&m,&n))
{
for(int i=1;i<=n;i++)scanf("%d",a+i);
memset(dp,0,sizeof(dp));
memset(pre,0,sizeof(pre));
int mx = 0;
for(int i=1;i<=m;i++)
{
for(int j=i;j<=n;j++)
dp[j] = max(pre[j-1] , dp[j-1]) + a[j];
mx = -inf;
pre[i-1] = mx;
for(int k=i;k<=n;k++)mx = max(dp[k], mx),pre[k] = mx;
}
cout< }
}