2011-06-10 19:42:18Morris
d832. 遊樂場
http://zerojudge.tw/ShowProblem?problemid=d832
內容 ：
遊樂場裡有一個遊戲：桌上放著 n 顆球，每顆球裡面閃亮亮著一個數字，有正有負，有些則是 0。
老闆說，這個遊戲可以一個人玩，也可以兩個人玩。
於是你開開心心地拉住朋友，跟老闆說要兩個人一起玩，
老闆說，請你先從這 n 個球中拿走連續的一些球，
然後再由你的朋友從剩下的球裡，同樣拿走連續的一些球。
接下來，你們手上的球的數字的總和，就是你們可以得到的獎金。
舉例來說，如果這一字排開的球上的數字是：
-3 5 6 7 -9 2 -1 4 3
那麼，可以得到最多獎金的拿法如下：
-3 (5 6 7) -9 [2 -1 4 3]
其中 [ ] 是你拿的球，而 ( ) 則是你朋友拿走的球，你們共可以得到 26 單位的獎金。
注意，你或你朋友當然可以什麼都不拿。
輸入說明
：
有多組測試資料，以 EOF 結束。
每組測試資料的第一行有兩個正整數 n (n<=10000) 和 m (m<2147483648)，
分別表示桌上的球的數量，以及玩這個遊戲必須預先支付給老闆的錢。
接下來有 n 個數字，每個數字的絕對值不會超過 1000。
輸出說明
：
輸出一個數字，表示你和你的朋友，能拿到的最高獎金是多少。
範例輸入 ：
9 100 -3 5 6 7 -9 2 -1 4 3 5 38 1 2 3 4 5
範例輸出 ：
26 15
提示
：
出處
：
(管理：shik)
作法 : DP
求兩段的 "連續元素和"，總和最大
http://www.cppleyuan.com/viewthread.php?tid=1240
/**********************************************************************************/
/* Problem: d832 "遊樂場" from */
/* Language: C */
/* Result: AC (3ms, 408KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-04 21:21:25 */
/**********************************************************************************/
#include<stdio.h>
main() {
int n, m, a, b;
while(scanf("%d %d", &n, &m) == 2) {
int A[10001] = {};
for(a = 0; a < n; a++)
scanf("%d", &A[a]);
int max[2][10001] = {}, mmax[10001] = {};
max[0][0] = A[0], mmax[0] = A[0];
for(a = 1; a < n; a++) {
if(max[0][a-1] > 0) max[0][a] = max[0][a-1] + A[a];
else max[0][a] = A[a];
if(max[0][a] > mmax[a-1]) mmax[a] = max[0][a];
else mmax[a] = mmax[a-1];
}
for(a = 1; a < 2; a++) {
for(b = 0; b < n; b++) max[0][b] = mmax[b];
max[1][a] = max[0][a-1] + A[a];
mmax[a] = max[1][a];
for(b = a+1; b < n; b++) {
if(max[0][b-1] > max[1][b-1])
max[1][b] = max[0][b-1] + A[b];
else max[1][b] = max[1][b-1] + A[b];
if(max[1][b] > mmax[b-1]) mmax[b] = max[1][b];
else mmax[b] = mmax[b-1];
}
}
printf("%d\n", mmax[n-1]);
}
return 0;
}
/*
http://www.cppleyuan.com/viewthread.php?tid=1240
*/
上一篇：d831. 畢業旅行
下一篇：d903. 數學達人