HDU 1024 Max Sum Plus Plus （基础dp）

/*基础dpA - Max Sum Plus Plus时间: 2017/02/18题意：在一组数取出m个不相交的区间，使区间和的总和最大。题解：dp[i][j]表示前i个数，分为j个区间和的总和最大的值dp[i][j] = max(dp[i-1][j]+a[i], max(dp[0……(i-1)][j-1])+a[i]);因为dp[i][j]只和dp[][j-1]和dp[i-1][j]有关，所以只需一维数组即可max(dp[0……(i-1)])可以在i-1层的时候处理出来，优化时间。*/#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <queue>#include <vector>#include <map>using namespace std;#define LL long long#define INF 0x3f3f3f3f#define PI acos(-1.0)#define E 2.71828#define MOD 1000000007#define N 1000010#define M 10010const double eps=1e-8;int a[N],dp[N],maxn[N];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(maxn,0,sizeof(maxn));        /*        未优化        for(int j = 1; j <= m; j++)        {            for(int i = j; i <= n; i++)            {                dp[i][j] = dp[i-1][j]+a[i];                for(int k = 1; k < i; k++)                    dp[i][j] = max(dp[i][j],dp[k][j]+a[i]);            }        */        int maxnn;        for(int i = 1; i <= m; i++)        {            maxnn = -INF;            for(int j = i; j <= n; j++)            {                dp[j] = max(dp[j-1],maxn[j-1])+a[j];                maxn[j-1] = maxnn;                maxnn = max(maxnn,dp[j]);            }            //PRintf("/n%d/n",maxnn);        }        printf("%d/n",maxnn);    }    return 0;}