題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1003 1003是喜聞樂(lè)見(jiàn)的最大連續(xù)子串和，經(jīng)典的動(dòng)態(tài)規(guī)劃題目，經(jīng)典歸經(jīng)典，我確實(shí)是剛剛做……在這道題中，我們需要保證的是在計(jì)算過(guò)程之中，計(jì)算的和是一直增加的，如果碰到了讓和減少的元素，直接把和更新為0，并且更新臨時(shí)首指針，每找到一個(gè)更優(yōu)的解，把真正的首指針和尾指針更新，整個(gè)過(guò)程中一直保證的是和是遞增的。注意我說(shuō)的是非全負(fù)的情況。
  view code
1 #include <cstdio>
2 int sum, s, t, ss, maxn, a[100100];
3 bool f;
4 int main(){
5 int t, n, p;
6 scanf("%d", &p);
7 for (int k = 1; k <= p; k++){
8 scanf("%d", &n);
9 f = 0, maxn = -9999999; sum = 0;
10 for (int i = 1; i <= n; i++){
11 scanf("%d", &a[i]);
12 if (a[i] >= 0) f = 1;
13 }
14 if (!f){
15 for (int i = 1; i <= n; i++)
16 if (a[i] > maxn){
17 maxn = a[i];
18 s = i;
19 }
20 printf("Case %d:\n%d %d %d\n", k, maxn, s, s);
21 }
22 else{
23 s = 1; t = 1; ss = 0;
24 for (int i = 1; i <= n; i++){
25 sum += a[i];
26 if (sum < 0){
27 ss = i;
28 sum = 0;
29 }
30 else if (sum > maxn){
31 maxn = sum;
32 s = ss + 1;
33 t = i;
34 }
35 }
36 printf("Case %d:\n%d %d %d\n", k, maxn, s, t);
37 }
38 if (k < p) printf("\n");
39 }
40 return 0;
41 題目鏈接： http://acm.hdu.edu.cn/showproblem.php?pid=1024 這道題厲害了，要求在n個(gè)數(shù)里面求m個(gè)最大子段和，要求最終的和最大，其實(shí)就是計(jì)算m次，因?yàn)檫@此不用記錄區(qū)間的首尾元素，所以其實(shí)比上一道題好寫(xiě)一些。
view code
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5 const int maxn = 1000100;
6 int n, m, ans, a[maxn], f[maxn], g[maxn];
7 int main(){
8 while (~scanf("%d%d", &m, &n)){
9 for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
10 memset(f, 0, sizeof(f));
11 memset(g, 0, sizeof(g));
12 for (int i = 1; i <= m; i++){
13 ans = -100 * maxn;
14 for (int j = i; j <= n; j++){
15 f[j] = max(f[j - 1], g[j - 1]) + a[j];
16 g[j - 1] = ans;
17 ans = max(ans, f[j]);
18 }
19 }
20 printf("%d\n", ans);
21 }
22 return 0;
23
|