HDU1024 Max Sum Plus Plus（DP）
February 16, 2016
题目链接
题意：给 n 个数，找出不交叉的 m 段，使所有段内元素和最大。
设 dp[ i ][ j ]表示前 i 个数中选 j 段的最大和，其中 i 在最后一段。
这样就有两种情况：
-
i 和前面的数在一段内，此时 dp[ i ][ j ] = dp[ i-1 ][ j ] + a[ i ][ j ]
-
i 自己单独一段，此时 dp[ i ][ j ] = max( dp[ k ][ j-1 ] ) + a[ i ][ j ] , 其中 j-1 =< k <=i-1 .
这样就写出了状态转移方程：dp[ i ][ j ] = max ( dp[ i-1 ][ j ] ， max( dp[ k ][ j-1 ] ) ) + a[ i ][ j ]， j-1 =< k <=i-1 .
此题 n 高达 10^6，开二维数组空间肯定不够，观察状态转移方程，其中 dp[ ][ j ]只用到了 dp[ ][ j ]和 dp[ ][ j-1 ]，也就是说 dp[ ][ 0 ]~dp[ ][ j-2 ]的值都不用了，也就是说 j 只开二维的就够了（听说叫滚动数组）。
再来看一看时间复杂度：n*n*m，再来观察方程，带 k 的这重循环是为了找最大值，这可以同步完成，避免了这层循环。时间复杂度为 n*m.
|
1
<div class="line number2 index1 alt1">
2
</div>
<div class="line number3 index2 alt2">
3
</div>
<div class="line number4 index3 alt1">
4
</div>
<div class="line number5 index4 alt2">
5
</div>
<div class="line number6 index5 alt1">
6
</div>
<div class="line number7 index6 alt2">
7
</div>
<div class="line number8 index7 alt1">
8
</div>
<div class="line number9 index8 alt2">
9
</div>
<div class="line number10 index9 alt1">
10
</div>
<div class="line number11 index10 alt2">
11
</div>
<div class="line number12 index11 alt1">
12
</div>
<div class="line number13 index12 alt2">
13
</div>
<div class="line number14 index13 alt1">
14
</div>
<div class="line number15 index14 alt2">
15
</div>
<div class="line number16 index15 alt1">
16
</div>
<div class="line number17 index16 alt2">
17
</div>
<div class="line number18 index17 alt1">
18
</div>
<div class="line number19 index18 alt2">
19
</div>
<div class="line number20 index19 alt1">
20
</div>
<div class="line number21 index20 alt2">
21
</div>
<div class="line number22 index21 alt1">
22
</div>
<div class="line number23 index22 alt2">
23
</div>
<div class="line number24 index23 alt1">
24
</div>
<div class="line number25 index24 alt2">
25
</div>
<div class="line number26 index25 alt1">
26
</div>
<div class="line number27 index26 alt2">
27
</div>
<div class="line number28 index27 alt1">
28
</div>
<div class="line number29 index28 alt2">
29
</div>
<div class="line number30 index29 alt1">
30
</div>
<div class="line number31 index30 alt2">
31
</div>
<div class="line number32 index31 alt1">
32
</div>
<div class="line number33 index32 alt2">
33
</div>
<div class="line number34 index33 alt1">
34
</div>
<div class="line number35 index34 alt2">
35
</div>
<div class="line number36 index35 alt1">
36
</div>
<div class="line number37 index36 alt2">
37
</div>
</td>
<td class="code">
<div class="container">
<div class="line number1 index0 alt2">
<code class="c preprocessor">#include<iostream></code>
</div>
<div class="line number2 index1 alt1">
<code class="c preprocessor">#include<cmath></code>
</div>
<div class="line number3 index2 alt2">
<code class="c preprocessor">#include<queue></code>
</div>
<div class="line number4 index3 alt1">
<code class="c preprocessor">#include<cstring></code>
</div>
<div class="line number5 index4 alt2">
<code class="c preprocessor">#include<string></code>
</div>
<div class="line number6 index5 alt1">
<code class="c preprocessor">#include<map></code>
</div>
<div class="line number7 index6 alt2">
<code class="c preprocessor">#include<stack></code>
</div>
<div class="line number8 index7 alt1">
<code class="c preprocessor">#include<set></code>
</div>
<div class="line number9 index8 alt2">
<code class="c preprocessor">#include<cstdio></code>
</div>
<div class="line number10 index9 alt1">
<code class="c preprocessor">#include<algorithm></code>
</div>
<div class="line number11 index10 alt2">
<code class="c keyword bold">using</code> <code class="c keyword bold">namespace</code> <code class="c plain">std;</code>
</div>
<div class="line number12 index11 alt1">
</div>
<div class="line number13 index12 alt2">
<code class="c color1 bold">int</code> <code class="c plain">a[1000005];</code>
</div>
<div class="line number14 index13 alt1">
<code class="c color1 bold">int</code> <code class="c plain">dp[1000005][2];</code>
</div>
<div class="line number15 index14 alt2">
</div>
<div class="line number16 index15 alt1">
<code class="c color1 bold">int</code> <code class="c plain">main(){</code>
</div>
<div class="line number17 index16 alt2">
<code class="c spaces"> </code><code class="c comments">//freopen("a.txt", "r", stdin);</code>
</div>
<div class="line number18 index17 alt1">
<code class="c spaces"> </code><code class="c color1 bold">int</code> <code class="c plain">n, m;</code>
</div>
<div class="line number19 index18 alt2">
<code class="c spaces"> </code><code class="c keyword bold">while</code><code class="c plain">(</code><code class="c functions bold">scanf</code><code class="c plain">(</code><code class="c string">"%d %d"</code><code class="c plain">, &m, &n) != EOF){</code>
</div>
<div class="line number20 index19 alt1">
<code class="c spaces"> </code><code class="c functions bold">memset</code><code class="c plain">(dp, 0, </code><code class="c keyword bold">sizeof</code><code class="c plain">(dp));</code>
</div>
<div class="line number21 index20 alt2">
<code class="c spaces"> </code><code class="c keyword bold">for</code><code class="c plain">(</code><code class="c color1 bold">int</code> <code class="c plain">i = 1; i <= n; i++)</code>
</div>
<div class="line number22 index21 alt1">
<code class="c spaces"> </code><code class="c functions bold">scanf</code><code class="c plain">(</code><code class="c string">"%d"</code><code class="c plain">, &a[i]);</code>
</div>
<div class="line number23 index22 alt2">
<code class="c spaces"> </code><code class="c color1 bold">int</code> <code class="c plain">ans = -1e9;</code>
</div>
<div class="line number24 index23 alt1">
<code class="c spaces"> </code><code class="c keyword bold">for</code><code class="c plain">(</code><code class="c color1 bold">int</code> <code class="c plain">j = 1; j <= m; j++){</code>
</div>
<div class="line number25 index24 alt2">
<code class="c spaces"> </code><code class="c color1 bold">int</code> <code class="c plain">maxx = -1e9;</code>
</div>
<div class="line number26 index25 alt1">
<code class="c spaces"> </code><code class="c keyword bold">for</code><code class="c plain">(</code><code class="c color1 bold">int</code> <code class="c plain">i = j; i <= n; i++){</code>
</div>
<div class="line number27 index26 alt2">
<code class="c spaces"> </code><code class="c plain">maxx = max(maxx, dp[i-1][0]);</code>
</div>
<div class="line number28 index27 alt1">
<code class="c spaces"> </code><code class="c plain">dp[i][1] = max(dp[i-1][1], maxx) + a[i];</code>
</div>
<div class="line number29 index28 alt2">
<code class="c spaces"> </code><code class="c keyword bold">if</code><code class="c plain">(j == m) ans = max(ans, dp[i][1]);</code>
</div>
<div class="line number30 index29 alt1">
<code class="c spaces"> </code><code class="c plain">}</code>
</div>
<div class="line number31 index30 alt2">
<code class="c spaces"> </code><code class="c keyword bold">for</code><code class="c plain">(</code><code class="c color1 bold">int</code> <code class="c plain">k = 0; k <= n; k++)</code>
</div>
<div class="line number32 index31 alt1">
<code class="c spaces"> </code><code class="c plain">dp[k][0] = dp[k][1];</code>
</div>
<div class="line number33 index32 alt2">
<code class="c spaces"> </code><code class="c plain">}</code>
</div>
<div class="line number34 index33 alt1">
<code class="c spaces"> </code><code class="c plain">cout << ans << endl;</code>
</div>
<div class="line number35 index34 alt2">
<code class="c spaces"> </code><code class="c plain">}</code>
</div>
<div class="line number36 index35 alt1">
<code class="c spaces"> </code><code class="c keyword bold">return</code> <code class="c plain">0;</code>
</div>
<div class="line number37 index36 alt2">
<code class="c plain">}</code>
</div>
</div>
</td>
</tr>
|