yxy

用户名：dotcpp0787179

访问量：435

签　名：

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

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

　　自我简介：

我不会

TA的其他文章

[搭配购买(buy)] 并查集 + dp动态规划（一维优化版）
浏览：23

dp动态规划 + 贪心算法 [信息学奥赛一本通T1260-拦截导弹]--NOIP1999 提高组 -- 最详细题解
浏览：60

多源bfs-[信息学奥赛一本通T1449-魔板]-洛谷绿
浏览：24

你可能喜欢

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

　　作者: yxy　　　　发表时间：2024-09-16 23:35:21 浏览：25　|　评论：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的其他文章

你可能喜欢

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

汽水瓶（C语言代码）

计算质因子（C++代码）100以内质数直接打表就好了

【偶数求和】（C++代码）

简单的a+b （C语言代码）

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

评论区

精彩推荐

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

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

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

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

Hello, world! （C语言代码）

链表数据求和操作（C语言代码）

简单的a+b （C语言代码）

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

小O的图案（C语言代码）

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

yxy

TA的其他文章

你可能喜欢

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

汽水瓶 （C语言代码）

计算质因子 （C++代码）100以内质数直接打表就好了

【偶数求和】 （C++代码）

简单的a+b （C语言代码）

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

评论区

精彩推荐

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

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

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

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

Hello, world! （C语言代码）

链表数据求和操作 （C语言代码）

简单的a+b （C语言代码）

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

小O的图案 （C语言代码）

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

汽水瓶（C语言代码）

计算质因子（C++代码）100以内质数直接打表就好了

【偶数求和】（C++代码）

　　评论区

链表数据求和操作（C语言代码）

小O的图案（C语言代码）