AcWing 898. 数字三角形

0、听课笔记

\(IOI\)原题，世界高中生信息学竞赛

需要进省队，进国家队，每年有4人代表中国参加\(IOI\)竞赛。

这道题如此简单，是因为是上世纪\(IOI\)的原题。

1、dfs

#include <bits/stdc++.h>

using namespace std;

const int N = 510;
int a[N][N];
int n;

//定义：计算以x,y为根的子树，返回子树的最长路径
//分析：任何一个x,y，要想获得答案，都需要了解它的左右儿子的情况，判断左右儿子哪个大，然后再把大的+自己就是答案
int dfs(int x, int y) {
    //左儿子，x+1,y
    //右儿子，x+1,y+1
    if (x == n + 1) return 0;//当走到n+1层，下面就不再有左右儿子了，所以是递归的出口，可以返回0
    //左子树最长路径计算：dfs(x+1,y)
    //右子树最长路径计算：dfs(x+1,y+1)
    return max(dfs(x + 1, y), dfs(x + 1, y + 1)) + a[x][y];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            scanf("%d", &a[i][j]);
    //计算以1,1为根的子树最长路径
    int res = dfs(1, 1);
    //输出
    printf("%d", res);
    return 0;
}

结果：简单样例通过

本题数据范围
\(1≤n≤500, −10000≤\)三角形中的整数\(≤10000\)

因为爆搜的时间复杂度是 \(2^{n-1}\),所以\(500\)的话就是\(2^{499}\)，肯定是\(TLE\)了!需要想办法优化。

2、记忆化搜索

#include <bits/stdc++.h>

using namespace std;
const int N = 510;

int a[N][N];
int f[N][N];
int n;

int dfs(int x, int y) {
    //如果算过，就直接返回
    if (~f[x][y]) return f[x][y];
    //左下方，x+1,y
    //右下方，x+1,y+1
    if (x == n + 1) return 0;
    //算过的都记录下来，别丢掉
    f[x + 1][y] = dfs(x + 1, y);
    f[x + 1][y + 1] = dfs(x + 1, y + 1);
    return max(f[x + 1][y], f[x + 1][y + 1]) + a[x][y];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            scanf("%d", &a[i][j]);

    //因为数字三角形中的数字都是大于0，所以初始化为-1，用来记录哪些位置搜索过，哪些还没有
    memset(f, -1, sizeof f);

    //调用 dfs
    int res = dfs(1, 1);
    printf("%d", res);
    return 0;
}

3、DP 动态规划

动态规划
(1)状态表示
\(f[i][j]\)

集合：从底向上走到\((i,j)\)所有路线的集合
属性：\(max\)

(2)状态计算
\(f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j]\)

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int f[N][N];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            scanf("%d", &f[i][j]);
    //自下向上，上面的准备依赖下面的，那么提前准备好下面的数据信息
    //如果求的是第n-1行的某个数字为根构成的数字三角形，那么问题该怎么处理呢？
    /*1、怎么初始化？
     其实base case是我们需要注意的一个问题：f[n][1]~f[n][n]根据实际要求，
     应该就是现在的本身，因为没有下一层。所以，本来可能需要进行一下base
     case初始化的，这里也不需要了。
     2、为什么是倒着循环的？
     因为我们发现f[i]其实是依赖于f[i+1]的，是先有f[i+1],再有f[i]，这还不倒序还能怎么办？
     正序倒序主要是看题意的实际情况。
    */
    for (int i = n - 1; i >= 1; i--)
        for (int j = 1; j <= i; j++)
            //此时枚举，遍历到的数据都是真实的数据，可以直接使用递推出上层的数字
            f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);

    //输出结果
    printf("%d", f[1][1]);
    return 0;
}