方格取数 (两条路径,使得取得的数字和为最大)
创始人
2024-02-26 05:42:14
0

设有 N×N 的方格图,我们在其中的某些方格中填入正整数,而其它的方格中则放入数字0。如下图所示:

某人从图中的左上角 A 出发,可以向下行走,也可以向右行走,直到到达右下角的 B 点。

在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。

此人从 A 点到 B 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。

输入格式

第一行为一个整数N,表示 N×N 的方格图。

接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该列上所放的数。

行和列编号从 1开始。一行“0 0 0”表示结束。

输出格式

输出一个整数,表示两条路径上取得的最大的和。

数据范围 N ≤ 10

输入样例:

8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0

输出样例:

67

思路:

        这个和需要一条路径的很像,只是我们不能简单的认为这是走了两次,因为第一次如果走了,会把某些数拿走,而我们并不知道哪些数被拿走了,所以,我们得考虑他们俩同时走。

如何表示他们俩同时走呢?可以用他们各自的坐标表示,例如:f[ i1 , j1 , i2 , j2 ]来表示,当第一个人走到(i1,j1)时且第二个人走到(i2,j2)的最大总和数字,用四个变量表示这个状态,那后面就有四重循环,我们想一想能不能优化,这里注意到题目的一个信息,那就是,两个人能不能重合,当两人重合时 i1+j1==i2+j2. 所以我们用一个变量k表示当前两个人走了多少步,就能减少一维来表达这个状态。

代码:

#include 
using namespace std;const int N = 15;int n;
int w[N][N];
int f[N * 2][N][N];int main()
{scanf("%d", &n);int a, b, c;while (cin >> a >> b >> c, a || b || c) w[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 >= 1 && j1 <= n && j2 >= 1 && j2 <= n){int t = w[i1][j1];if (i1 != i2) t += w[i2][j2];int &x = f[k][i1][i2];//&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);}}printf("%d\n", f[n + n][n][n]);return 0;
}

 

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播,要解决的几个问题是:1&...
Windows10添加群晖磁盘... 在使用群晖NAS时,我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
Fluent中创建监测点 1 概述某些仿真问题,需要创建监测点,用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装(Wind... 前言:刚换了一台电脑,里面所有东西都需要重新配置,习惯了所...
MFC文件操作  MFC提供了一个文件操作的基类CFile,这个类提供了一个没有缓存的二进制格式的磁盘...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章,在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
有效的括号 一、题目 给定一个只包括 '(',')','{','}'...
【Ctfer训练计划】——(三... 作者名:Demo不是emo  主页面链接:主页传送门 创作初心ÿ...