[已解决]数字三角型

柿子饼同学

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int main(){
   
5.         ios::sync_with_stdio(0);
   
6.         int r;
   
7.         cin >> r;
   
8.         vector<vector<int>> tri(r+1, vector<int>(r+1));
   
9.         for(int i = 0; i < r; i++){
   
10.                 for(int j = 0; i <= i; j++){
    
11.                         cin >> tri[i][j];
    
12.                 }
    
13.         }
    
14.         
    
15.         for(int i = r-2; i >= 0; i--){
    
16.                 for(int j = 0; i <= i; j++){
    
17.                         tri[i][j] += max(tri[i+1][j], tri[i+1][j+1]);
    
18.                 }
    
19.         }
    
20.         cout << tri[0][0];
    
21.         return 0;
    
22. }

复制代码

大伙帮忙看看~

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

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
这个题目跟你之前几题相似，可以用之前递归方法找出最优解

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int main(){
   
5.         ios::sync_with_stdio(0);
   
6.         int r;
   
7.         cin >> r;
   
8.         vector<vector<int>> tri(r, vector<int>(r));
   
9.         for(int i = 0; i < r; i++){
   
10.                 for(int j = 0; j <= i; j++){
    
11.                         cin >> tri[i][j];
    
12.                 }
    
13.         }
    
14.         for(int i = r-2; i >= 0; i--){
    
15.                 for(int j = 0; j <= i; j++){
    
16.                         tri[i][j] += max(tri[i+1][j], tri[i+1][j+1]);
    
17.                 }
    
18.         }
    
19.         cout << tri[0][0];
    
20.         return 0;
    
21. }

复制代码

最后用这个方法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]

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <vector>
   
4. 
   
5. using std::vector, std::max;
   
6. int foo(vector<vector<short>> arr, int x = 0, int y = 0) {
   
7.         if (x >= arr.size()) return 0;
   
8.         return arr[x][y] + max(foo(arr, x + 1, y), foo(arr, x + 1, y + 1));
   
9. }
   
10. 
    
11. using std::cin, std::cout, std::endl;
    
12. int main(void) {
    
13.         short r, num;
    
14.         cin >> r;
    
15.         vector<short> temp;
    
16.         vector<vector<short>> arr(r, temp);
    
17.         for (int i = 0; i < r; ++i) {
    
18.                 for (int j = 0; j < i + 1; ++j) {
    
19.                         cin >> num;
    
20.                         arr[i].push_back(num);
    
21.                 }
    
22.         }
    
23.         cout << foo(arr) << endl;
    
24.         return 0;
    
25. }

复制代码

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

复制代码