[已解决]数字三角型

柿子饼同学

题目 : https://www.luogu.com.cn/problem/P1216
我的代码不知道怎么回事, 不输出...

#include <bits/stdc++.h>
using namespace std;

int main(){
        ios::sync_with_stdio(0);
        int r;
        cin >> r;
        vector<vector<int>> tri(r+1, vector<int>(r+1));
        for(int i = 0; i < r; i++){
                for(int j = 0; i <= i; j++){
                        cin >> tri[i][j];
                }
        }
        
        for(int i = r-2; i >= 0; i--){
                for(int j = 0; i <= i; j++){
                        tri[i][j] += max(tri[i+1][j], tri[i+1][j+1]);
                }
        }
        cout << tri[0][0];
        return 0;
}

大伙帮忙看看~

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-5-4 13:52:49

柿子饼同学 发表于 2022-5-4 13:37
最后用这个方法AC了
但是还是不知道递归的初始状态怎么写...

也行，本来想说用递归方法的（二叉树），但又发现重复子问题，还是像你的代码一样用循环比较好，想到 r <= 1000 行，最大 500500个数字，用递归也不合适，消耗资源太大了。

跳转到最佳答案楼层

柿子饼同学

就是从倒数第二层开始, 每次给 i, j 加上下面两个数字中的大者
这样循环之后第一层就是最大值了

傻眼貓咪

柿子饼同学 发表于 2022-5-4 12:16
就是从倒数第二层开始, 每次给 i, j 加上下面两个数字中的大者
这样循环之后第一层就是最大值了

这个题目跟你之前几题相似，可以用之前递归方法找出最优解

柿子饼同学

傻眼貓咪 发表于 2022-5-4 12:27
这个题目跟你之前几题相似，可以用之前递归方法找出最优解

#include <bits/stdc++.h>
using namespace std;

int main(){
        ios::sync_with_stdio(0);
        int r;
        cin >> r;
        vector<vector<int>> tri(r, vector<int>(r));
        for(int i = 0; i < r; i++){
                for(int j = 0; j <= i; j++){
                        cin >> tri[i][j];
                }
        }
        for(int i = r-2; i >= 0; i--){
                for(int j = 0; j <= i; j++){
                        tri[i][j] += max(tri[i+1][j], tri[i+1][j+1]);
                }
        }
        cout << tri[0][0];
        return 0;
}

最后用这个方法AC了
但是还是不知道递归的初始状态怎么写...

傻眼貓咪

柿子饼同学 发表于 2022-5-4 13:37
最后用这个方法AC了
但是还是不知道递归的初始状态怎么写...

也行，本来想说用递归方法的（二叉树），但又发现重复子问题，还是像你的代码一样用循环比较好，想到 r <= 1000 行，最大 500500个数字，用递归也不合适，消耗资源太大了。

柿子饼同学

傻眼貓咪 发表于 2022-5-4 13:52
也行，本来想说用递归方法的（二叉树），但又发现重复子问题，还是像你的代码一样用循环比较好，想到 r

哈哈哈二叉树我没学过...

傻眼貓咪

柿子饼同学 发表于 2022-5-4 14:56
哈哈哈二叉树我没学过...

我尝试用递归做出动态规划，没想到也行，但不知其它数据可以不可以正常 AC 呢？
动态规划公式：sum[x][y]=max(sum[x+1][y],sum[x+1][y+1])+arr[x][y]

#include <iostream>
#include <algorithm>
#include <vector>

using std::vector, std::max;
int foo(vector<vector<short>> arr, int x = 0, int y = 0) {
        if (x >= arr.size()) return 0;
        return arr[x][y] + max(foo(arr, x + 1, y), foo(arr, x + 1, y + 1));
}

using std::cin, std::cout, std::endl;
int main(void) {
        short r, num;
        cin >> r;
        vector<short> temp;
        vector<vector<short>> arr(r, temp);
        for (int i = 0; i < r; ++i) {
                for (int j = 0; j < i + 1; ++j) {
                        cin >> num;
                        arr[i].push_back(num);
                }
        }
        cout << foo(arr) << endl;
        return 0;
}

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
30