十五月明

用户名：dotcpp0605328

访问量：5433

签　名：

等　　级
排　　名	319
经　　验	5465
参赛次数	0
文章发表	87
年　　龄	18
在职情况	学生
学　　校	曲阜师范大学
专　　业	人工智能

　　自我简介：

Easy

TA的其他文章

信息学奥赛一本通T1346-亲戚(relation) 并查集此题有毒
浏览：7

信息学奥赛一本通T1347-格子游戏并查集
浏览：5

团伙(group) 并查集
浏览：57

你可能喜欢

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

方格取数双线程dp

　　作者: 十五月明　　　　发表时间：2024-10-27 16:17:14 浏览：7　|　评论：0　

原题链接：蓝桥杯算法训练VIP-方格取数

#include<iostream>
    #include<algorithm>
    using namespace std;
    int map[15][15]={0};
    int dp[15][15][15][15]={0};
    int main()
    {
        int n; cin >> n;
        int dx,dy,dv;
        while (cin>>dx>>dy>>dv)
        {
            if(dx==0&&dy==0&&dv==0)
                break;
            map[dx][dy]=dv;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int x=1;x<=n;x++)
                    for (int y=1;y<=n;y++)//遍历每一步
                    {
                        if (i + j != x + y)
                            continue;//确保两人都是一人走一步
                        int m1=max(dp[i-1][j][x-1][y],dp[i][j-1][x][y-1]);
                        int m2=max(dp[i-1][j][x][y-1],dp[i][j-1][x-1][y]);
                        dp[i][j][x][y]=max(m1,m2);
                        //两者走的前一步的所有情况
                        if (i == x && j == y)
                            dp[i][j][x][y] += map[i][j];//如果两人走到同一个地方，因为走过后的地方置0，那么就只加权一次
                        else
                            dp[i][j][x][y] += map[i][j] + map[x][y];//加权
                    }
        cout << dp[n][n][n][n];
        return 0;
    }
int dp[15][15][15][15]：把一个人走两次，看成两个人一起走，因为要记录两个人，所以用双线程dp。dp[i][j][x][y]表示一人走到map[i][j]另一人走到map[x][y]得到的最大和
1.枚举当前位置（i,j）和（x,y）
2.到达当前位置只有四种情况，上上，左左，上左，左上
3.判断当前的两个位置是否相同
4.进行求最大值

0.0分

1 人评分

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

十五月明

TA的其他文章

你可能喜欢

汽水瓶（C语言代码）

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

汽水瓶（C语言代码）

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

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

方格取数双线程dp

评论区

精彩推荐

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

C语言训练-最大数问题（C语言代码）.........关于-1

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

高精度加法（C++代码）（大数加法）

C语言训练-字符串正反连接（C语言代码）

三角形（C语言代码）

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

字符逆序（C语言代码）

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

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

十五月明

TA的其他文章

你可能喜欢

汽水瓶 （C语言代码）

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

汽水瓶 （C语言代码）

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

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

方格取数 双线程dp

评论区

精彩推荐

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

C语言训练-最大数问题 （C语言代码）.........关于-1

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

高精度加法 （C++代码）（大数加法）

C语言训练-字符串正反连接 （C语言代码）

三角形 （C语言代码）

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

字符逆序 （C语言代码）

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

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

汽水瓶（C语言代码）

汽水瓶（C语言代码）

方格取数双线程dp

　　评论区

C语言训练-最大数问题（C语言代码）.........关于-1

高精度加法（C++代码）（大数加法）

C语言训练-字符串正反连接（C语言代码）

三角形（C语言代码）

字符逆序（C语言代码）