柿子饼同学 发表于 2022-5-4 12:14:56

数字三角型

题目 : 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;
                }
      }
      
      for(int i = r-2; i >= 0; i--){
                for(int j = 0; i <= i; j++){
                        tri += max(tri, tri);
                }
      }
      cout << tri;
      return 0;
}
大伙帮忙看看~

柿子饼同学 发表于 2022-5-4 12:16:26

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

傻眼貓咪 发表于 2022-5-4 12:27:06

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

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

柿子饼同学 发表于 2022-5-4 13:37:56

傻眼貓咪 发表于 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;
                }
      }
      for(int i = r-2; i >= 0; i--){
                for(int j = 0; j <= i; j++){
                        tri += max(tri, tri);
                }
      }
      cout << tri;
      return 0;
}
最后用这个方法AC了
但是还是不知道递归的初始状态怎么写...

傻眼貓咪 发表于 2022-5-4 13:52:49

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

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

柿子饼同学 发表于 2022-5-4 14:56:43

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

哈哈哈二叉树我没学过...{:10_266:}

傻眼貓咪 发表于 2022-5-4 17:32:00

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

我尝试用递归做出动态规划，没想到也行，但不知其它数据可以不可以正常 AC 呢？
动态规划公式：sum=max(sum,sum)+arr
#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 + 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.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
页: [1]
查看完整版本: 数字三角型