题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1003 1003是喜闻乐见的最大连续子串和，经典的动态规划题目，经典归经典，我确实是刚刚做……在这道题中，我们需要保证的是在计算过程之中，计算的和是一直增加的，如果碰到了让和减少的元素，直接把和更新为0，并且更新临时首指针，每找到一个更优的解，把真正的首指针和尾指针更新，整个过程中一直保证的是和是递增的。注意我说的是非全负的情况。
  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个数里面求m个最大子段和，要求最终的和最大，其实就是计算m次，因为这此不用记录区间的首尾元素，所以其实比上一道题好写一些。
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
|