a1007

题目大意

给出序列片段最大的和。

解决方法

使用动态规划,

第一步构建d[p]初始值

1
d[0]=cost[0];

第二步检查是不是所有的都是负数

如果是,那么直接返回0

1
2
3
4
5
6
7
8
9
10
11
int flag=0;
    for (int j = 0; j < n; ++j) {
        if (cost[j]>=0){
            flag= 1;
        }
    }
    if (flag==0){
//
        printf("0 %d %d",cost[0],cost[n-1]);
        return 0;
    }

写出转移态方程

如果d[j-1]+a[j]>a[j],d[j]=d[j-1]+a[j],否则d[j]=a[j]

1
2
3
4
5
6
7
8
9
10
11
12
for (int k = 1; k < n; ++k) {
        if (d[k-1]+cost[k]>cost[k]){
//
            d[k]=d[k-1]+cost[k];
            s[k]=s[k-1];
        } else{
            d[k]=cost[k];
//            更新起点
            s[k]=k;

        }
    }

总体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <cmath>
#include <set>
#include <stack>
#include <queue>

//cin用多了超市

using namespace std;
const int maxn=100100;

int main() {
    int n;
    cin>>n;
    int cost[n];
    for (int i = 0; i < n; ++i) {
        scanf("%d",&cost[i]);
    }

//    首先检查睡吧睡吧全是负数
    int flag=0;
    for (int j = 0; j < n; ++j) {
        if (cost[j]>=0){
            flag= 1;
        }
    }
    if (flag==0){
//
        printf("0 %d %d",cost[0],cost[n-1]);
        return 0;
    }
    //构建转移方程
//    首先是初始化d【0】=a【0】
//    然后是d【i】=a【i】或者是d【i】=d【i-1】+a【i】
    int d[n];
    d[0]=cost[0];
    int s[n];
//    这是起点
    for (int k = 1; k < n; ++k) {
        if (d[k-1]+cost[k]>cost[k]){
//
            d[k]=d[k-1]+cost[k];
            s[k]=s[k-1];
        } else{
            d[k]=cost[k];
//            更新起点
            s[k]=k;

        }
    }
    int p=0;
    for (int l = 0; l <n ; ++l) {
        if (d[l]>d[p]){
            p=l;
        }
    }
    cout<<d[p]<<" "<<cost[s[p]]<<" "<<cost[p];
    return 0;
}