[已解决]数字三角型

柿子饼同学

题目 : 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: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:52
也行，本来想说用递归方法的（二叉树），但又发现重复子问题，还是像你的代码一样用循环比较好，想到 r

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