Hdu 1024 Max Sum Plus Plus (dp)

题目链接：

题目描述：

　　给出n个数，问m段连续子序列的和相加最大是多少？

解题思路：

　　dp[i][j]表示把前i个元素(包括第i个)，分成j段的最大和。状态转移方程就是dp[i][j] = max (dp[i-1][j] + arr[j], max( dp[k][j-1]) + arr[j])，其中0<k<i。(第i个元素是保存在第j段，还是自己单独成段)

　　由于1<=n<=1000,000。n*n的数组肯定会爆炸，所以要对方程进行降维。观察可得，我们可以在状态转移的时候保存max(dp[k][j-1]),然后第一维就可以省去了。

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

Hdu 1024 Max Sum Plus Plus (dp)

相关推荐