yxy

用户名：dotcpp0787179

访问量：497

签　名：

竞赛交流论坛： blog.qzcy2.top 欢迎来撩！

等　　级
排　　名	976
经　　验	3389
参赛次数	3
文章发表	23
年　　龄	1
在职情况	学生
学　　校	内江师范学院
专　　业	纳西妲系

　　自我简介：

我不会

TA的其他文章

[金银岛]自定义排序优先'均权'最大--我看题解都太复杂辣
浏览：56

杀到这九天十地无人敢称尊,直到身边再无一人能陪我征战,叶天帝不过如此
浏览：38

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

dp--数字三角形模型//闫氏dp法[方格取数]-NOIP2000 提高组-洛谷绿题

　　作者: yxy　　　　发表时间：2024-09-16 23:35:21 浏览：29　|　评论：1　

原题链接：信息学奥赛一本通T1277-方格取数

# 数字三角形模型 闫氏dp法
## 本题测试点数据是错的 想要练习的同学可到 链接：[方格取数](https://www.xfxcy.com/p/T1277 "方格取数")尝试

###### 数字三角形基础模板 ： 链接： [数字金字塔](https://www.dotcpp.com/oj/problem2127.html "数字金字塔") 题解链接 ： [数字三角形基础模板题解](https://blog.dotcpp.com/a/106383 "数字三角形基础模板题解")
![](/image_editor_upload/20240916/20240916112659_82376.jpg)

此题和传统的题不一 是同时走两条路径 并且每个格子里的数只能用一次
###### 判断两条路径重合 只有在i1 + j1 = i2 + j2 的时候才有可能 但是 反之不然 感兴趣的同学可以画图试试

相关思路图上很清楚 那就直接上代码：
###### Code：
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long  //个人习惯 有备无患

using namespace std;
const int N = 15;
int g[N][N];
int f[N * N][N][N];   //动态规划数组
int n;

signed main()
{
    cin >> n;
    int a , b , c;
    while (cin >> a >> b >> c , a || b || c) g[a][b] = c;  //abc为零 停止输入

for (int k = 2 ; k <= n + n ; k ++ )
    {
        for (int i1 = 1 ; i1 <= n ; i1 ++ )
        {
            for (int i2 = 1 ; i2 <= n ; i2 ++ )
            {
                int j1 = k - i1 , j2 = k - i2;
                if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
                {
                    int t = g[i1][j1];
                    if (i1 != i2) t += g[i2][j2];
                    int &x = f[k][i1][i2];  //&x代表一个临时的三位数组 懒得写这么长了
                    x = max(x , f[k - 1][i1 - 1][i2 - 1] + t); //状态转移
                    x = max(x , f[k - 1][i1 - 1][i2] + t);
                    x = max(x , f[k - 1][i1][i2 - 1] + t);
                    x = max(x , f[k - 1][i1][i2] + t);
                }
            }
        }
    }
    
    cout << f[n + n][n][n] << endl;

return 0;
}
```

###### 题解不宜 求赞orz

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

109徐守佳

░░░░░░░░░░░█░█
░░░░░░░░░░░█░█
░░░░░░░░░░█░░█
░░░░░░░░░█░░░█
███████▄▄█░░░██████▄
▓▓▓▓▓▓█░░░░░░░░░░░░█
▓▓▓▓▓▓█░░░░░░░░░░░░█
▓▓▓▓▓▓█░░░░░░░░░░░░█
▓▓▓▓▓▓█░░░░░░░░░░░░█
▓▓▓▓▓▓█░░░░░░░░░░░░█
▓▓▓▓▓▓█████░░░░░░░░█
██████▀░░░▀▀██████▀

2024-09-16 23:56:45

yxy

TA的其他文章

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

【亲和数】（C语言代码）

dp--数字三角形模型//闫氏dp法[方格取数]-NOIP2000 提高组-洛谷绿题

评论区

精彩推荐

哥德巴赫曾猜测（C语言代码）

大神老白（C语言代码）

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

WU-陶陶摘苹果2 （C++代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

矩阵加法（C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

良心推荐——>题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言描述——简单明了，时间复杂度低）

敲七（C++代码）

yxy

TA的其他文章

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

【明明的随机数】 （C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

【亲和数】 （C语言代码）

dp--数字三角形模型//闫氏dp法[方格取数]-NOIP2000 提高组-洛谷绿题

评论区

精彩推荐

哥德巴赫曾猜测 （C语言代码）

大神老白 （C语言代码）

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

WU-陶陶摘苹果2 （C++代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

矩阵加法 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

良心推荐——>题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言描述——简单明了，时间复杂度低）

敲七 （C++代码）

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

【亲和数】（C语言代码）

　　评论区

哥德巴赫曾猜测（C语言代码）

大神老白（C语言代码）

矩阵加法（C语言代码）

敲七（C++代码）