hdu Max Sum Plus Plus(dp+滚动数组)

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <limits.h> 
 5 #include <algorithm>
 6 #include <iostream>
 7 #include <ctype.h>
 8 #include <iomanip>
 9 #include <queue>
10 #include <map>
11 #include <stdlib.h>
12 using namespace std;
13 
14 #define Max(a,b) ((a)>(b)?(a):(b))  
15 #define M 1000001 
16 
17 int dp[M],t[M],num[M],n,m;
18 
19 int main()
20 {
21     while(~scanf("%d %d",&m,&n)){
22         int i,j;
23         for(i=1;i<=n;i++)
24             scanf("%d",&num[i]);
25         memset(dp,0,sizeof(dp));
26         memset(t,0,sizeof(t));
27         int max;
28         for(i=1;i<=m;i++){
29             max=INT_MIN;
30             for(j=i;j<=n;j++){
31                 dp[j]=Max(dp[j-1],t[j-1])+num[j];
32                 t[j-1]=max;
33                 max=Max(dp[j],max);
34             }
35             t[j-1]=max;
36         }
37         printf("%d\n",max);
38     }
39 }