P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles

该题的思路是，从底层数开始，逐渐向上更新。

例如：
1

​ 2 3

5 6 7

经过一次更新后，从倒数第二层开始，对于2，它的两个孩子5和6中6更大，于是2更新为2+6=8，同理3更新为10之后就有：

​ 1

​ 8 10

5 6 7

层数向上移动一层，接着从第一层继续执行上述操作，1+10=11，所以有：

​ 11

​ 8 10

5 6 7

输出第一个数就是最大路径和，1 + 3 + 7 = 11

很容易发现，每一次更新，把被更新的数变成由它向下辐射的三角中的，最大路径和。例如上例中的三角3 6 7, 3经过更新后变成三角3 6 7的最大路径和，3 + 7 = 10。采用这种分治的思想，从小到大，递归得到由第一个数向下辐射的三角的最大路径和。

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
#include<iostream>
#include<algorithm>

int f[500510];
int r, j;

int main(){
    std::cin >> r;
    int cnt = r * (r + 1) / 2;
    for(int i = 1; i <= cnt; i++){
        std::cin >> f[i];
    }
    cnt -= r;//从倒数第二层开始更新
    for(int i = r - 1; i >= 1; i--){//'i' is floor
        j = i;
        cnt -= i;
        while(j > 0){
            f[cnt + j] += std::max(f[cnt + j + i], f[cnt + j + i + 1]);
            j--;
        }
    }
    // int c = 1;
    // for(int i = 1; i <= r; i++){
    //     for(int j = 1; j <= i; j++){
    //         std::cout << f[c] << " ";
    //         c++;
    //     }
    //     std::cout << "\n";
    // }
    //输出样例测试，打印出更新后的三角塔
    std::cout << f[1];
    return 0;
}

P1048 [NOIP2005 普及组] 采药

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<algorithm>

int f[1100] = {0};

int main(){
    int time, num, t, value;
    std::cin >> time >> num;
    for(int i = 1; i <= num; i++){
        std::cin >> t >> value;
        for(int j = time; j >= t; j--){
            f[j] = std::max(f[j], f[j - t] + value);
        }
    }
    std::cout << f[time];
    return 0;
}

P2196 [NOIP1996 提高组] 挖地雷

有向无边权，有点权的图。

思路是，设置一个数组max，存储第 i 个节点前最大地雷和，同理于上述背包问题里的数组 f。

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
#include<iostream>
#include<algorithm>

int num, t, ans = 0;
int f[100] = {0}, max[100] = {0};
int path[30][30] = {0};
int pre[30] = {0};
int sum = 0;

int main(){
    std::cin >> num;
    for(int i = 1; i <= num; i++){
        std::cin >> f[i];
    }
    for(int i = 1; i <= num - 1; i++){
        for(int j = i + 1;j <= num; j++){
            std::cin >> path[i][j];
        }
    }
    for(int i = 1; i <= num; i++){
        for(int j = 1; j <= num; j++){
            //遍历每条路径
            if(path[j][i] && max[j] > max[i]){
                max[i] = max[j];
                pre[i] = j;
            }
        }
        max[i] += f[i];
        if(max[i] > ans){
            ans = max[i];
            t = i;
        }
    }
    int cnt = 1;
    for(int i = t; i != 0; i = pre[i], cnt++){
        f[cnt] = i;
    }
    for(int i = cnt - 1; i >= 1; i--){
        std::cout << f[i] << ' ';
    }
    std::cout << "\n"<< ans;
    return 0;
}

P1434[SHOI2002] 滑雪

这是一道深度搜索问题，DFS。

通过遍历每个节点，然后往深处搜索最大路径，其中搜索过的路径会被数组f[] []记录

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
#include<iostream>
#include<algorithm>

int map[110][110] = {0};
int f[110][110] = {0};
int r, c, ans = 0;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int dfs(int x, int y){
    if(f[x][y]){}//如果搜过
    else{
        f[x][y] = 1;//最小也有一格
        for(int i = 0; i <4; i++){
            int x0 = x + dx[i], y0 = y + dy[i];
            if(x0 > 0 && y0 >0 && x0 <= r && y0 <= c){
                if(map[x][y] > map[x0][y0]){
                    f[x][y] = std::max(f[x][y], dfs(x0, y0) + 1);
                }
            }
        }
    }
    return f[x][y];
}

int main(){
    std::cin >> r >> c;
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            std::cin >> map[i][j];
        }
    }
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            ans = std::max(ans, dfs(i, j));
        }
    }
    std::cout << ans;
    return 0;
}