AcWing 1027. 方格取数（高难度线性dp）

╰半夏微凉° 2022-08-28 11:49 143阅读 0赞

本来想着先用dp获取最大值，然后标记，最后再dp一遍，貌似可以实现。

正解：两条路线每次走的步数是一样的，k = i1 + j1 = i2 + j2

比较来自四个方位的点的大小

引用的目的是为了让 dp 随之改变

#include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int v[15][15];
    int dp[50][15][15];
    
    int main()
    { 
        int n, a, b, c;
        
        cin >> n;
        
        while (cin >> a >> b >> c and a|b|c) v[a][b] = c;
        
        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 <= n and j1 >= 1 and j2 <= n and j2 >= 1)
                    { 
                        int &x = dp[k][i1][i2];
                        int t = v[i1][j1];
                        if(i1!=i2) t += v[i2][j2];
                        
                        x = max(x, dp[k-1][i1-1][i2-1] + t);
                        x = max(x, dp[k-1][i1-1][i2] + t);
                        x = max(x, dp[k-1][i1][i2-1] + t);
                        x = max(x, dp[k-1][i1][i2] + t);
                    }
                }
            }
        }
        cout << dp[n+n][n][n];
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，143人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|动态规划 | 线性dp | 数字三角形模型No.1】AcWing1015.摘花生 & AcWing898.数字三角形 & AcWing1027.方格取数 & AcWing275.传纸条

【算法|动态规划 | 线性dp | 数字三角形模型No.1】AcWing1015.摘花生 & AcWing898.数字三角形 & AcWing1027.方格取数 & Ac...

傷城~/ 2024年04月27日 06:52/ 0 赞/ 55 阅读

相关数字三角形模型 AcWing 1027. 方格取数

数字三角形模型 AcWing 1027. 方格取数原题链接 [AcWing 1027. 方格取数][AcWing 1027.] 算法标签 DP 线性DP

àì夳堔傛蜴生んèń/ 2023年09月28日 13:52/ 0 赞/ 99 阅读

相关 AcWing 1015. 摘花生（线性dp）

include <iostream> include <cstring> include <algorithm> using name

àì夳堔傛蜴生んèń/ 2022年09月13日 04:16/ 0 赞/ 125 阅读

相关 AcWing 1027. 方格取数（高难度线性dp）

本来想着先用dp获取最大值，然后标记，最后再dp一遍，貌似可以实现。正解：两条路线每次走的步数是一样的，k = i1 + j1 = i2 + j2 比较来自四个方位的点的

╰半夏微凉°/ 2022年08月28日 11:49/ 0 赞/ 144 阅读

相关 Hrbust 1214 方格取数（双线程dp）

题目链接： [Hrbust 1214][] 题解：双线程dp。设dp\[k\]\[i\]\[j\]，其中k表示走了k步，i表示第一个人在i 列，j表示第二个人在

柔光的暖阳◎/ 2022年06月14日 08:17/ 0 赞/ 151 阅读

相关方格取数（状压DP）

include<cstdio> include<iostream> include<algorithm> using namespace std

系统管理员/ 2022年05月28日 07:55/ 0 赞/ 234 阅读

相关 NOIP 2000 方格取数(多线程DP)

题目描述设有N\N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）： ![pimg1026_1.jpg][] 某

末蓝、/ 2022年05月17日 10:38/ 0 赞/ 267 阅读

相关方格取数

题目描述设有N \\times NN×N的方格图(N \\le 9)(N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字00。如下图所示（见样例）:

心已赠人/ 2022年03月07日 10:52/ 0 赞/ 352 阅读

相关洛谷P1004 方格取数[多维dp]

题目描述设有N\N的方格图(N<=9)，我们将其中的某些方格中填入正整数，而其他的方格中则放人数字0。如下图所示（见样例）： A 0 0 0 0 0 0 0

客官°小女子只卖身不卖艺/ 2021年09月20日 11:58/ 0 赞/ 357 阅读

相关 AcWing 1027. 方格取数【DP动态规划】c++版题解

题目设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示： ![在这里插入图片描述][20201129185222

水深无声/ 2021年07月24日 18:47/ 0 赞/ 529 阅读