hdu 1024 Max Sum Plus Plus

http://acm.hdu.edu.cn/showproblem.php?pid=1024

状态转移方程： dp[j]=max(dp[j-1]+a[j],pre[j-1]+a[j]);

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 1000010
 5 #define ll int
 6 using namespace std;
 7 const int inf=1<<29;
 8 
 9 ll dp[maxn],pre[maxn];
10 int a[maxn];
11 int n,m;
12 ll max2;
13 
14 ll max1(ll a,ll b)
15 {
16     if(a>b) return a;
17     return b;
18 }
19 
20 int main()
21 {
22     while(scanf("%d%d",&m,&n)!=EOF)
23     {
24         for(int i=1; i<=n; i++)
25         {
26             scanf("%d",&a[i]);
27         }
28         memset(dp,0,sizeof(dp));
29         memset(pre,0,sizeof(pre));
30         for(int i=1; i<=m; i++)
31         {
32             max2=-inf;
33             for(int j=i; j<=n; j++)
34             {
35                 dp[j]=max(dp[j-1]+a[j],pre[j-1]+a[j]);
36                 pre[j-1]=max2;
37                 max2=max(max2,dp[j]);
38             }
39         }
40         printf("%d
",max2);
41     }
42     return 0;
43 }

View Code