标签：传送门 探险 int 坐标 宝藏 遗迹 define
链接：https://ac.nowcoder.com/acm/contest/56825/D
来源：牛客网
题目描述
小Z是一名探险家。有一天，小Z误入了一个魔法遗迹。以下是该遗迹的具体组成：
- 在 x轴和 y 轴构成的平面上，满足在 $$1≤x≤n，1≤y≤m$$的区域中(坐标(x,y)表示平面上的第x行的第y列)，每个整数坐标 (x,y)都有一个宝藏，坐标为(i,j)的宝藏的价值为ai,j（请注意，宝藏的价值可以为负）。换句话说，这个区域上的整点都有一个宝藏。
- 对于任意一对点 (x1,y1)和 (x2,y2)，如果它们的横坐标相等，纵坐标之差为 1，则纵坐标小的点有一条道路可以到达纵坐标大的点，或者它们的纵坐标相等，横坐标之差为 1，则横坐标小的点有一条道路可以到达横坐标大的点。换句话说，(x,y)可以到达(x+1,y)或(x,y+1)，反之不然。
- 遗迹的入口在(1,1)，出口在(n,m)，小Z从入口进入后从出口离开，在移动的过程中他会将他所遇到的所有宝藏全部收集起来。
小Z想知道从进入到离开遗迹，他在离开遗迹时所能获得的宝藏的价值的和最大为多少。
作为一个有智慧的探险家，小Z当然会解决这个问题。但是由于这个遗迹具有魔法，问题就变得不是那么简单了。
在小Z进入该遗迹前，遗迹的魔法发动，它会在若干个具有宝藏的位置生成一个传送门。若小Z所在的坐标有传送门，则他可以通过这个传送门到达其它任意一个具有传送门的位置(当然，他也可以选择不使用传送门)，并且小Z在使用一次传送门后，所有的传送门都会消失。换句话说，小Z只能最多使用一次传送门。
该遗迹具有魔法，每当小Z离开某个整点，该整点就会重新生成一个价值为ai,j的宝藏。
小Z会进入T次该遗迹。请你帮助小Z计算出，对于每次进入遗迹，在给定传送门的坐标的情况下，他在离开遗迹时所能获得的宝藏的价值的和最大为多少？
输入描述:
第一行包含两个正整数 n,m $$(2≤n≤103，2≤m≤103)$$，变量的含义如题意所示。
接下来有nn行，每行有mm个整数，其中第ii行第jj列的数字代表坐标(i,j)(i,j)的宝藏的价值$$ai,j (∣ai,j∣≤109)$$。
接下来有一个数字$$T (1≤T≤103)$$，表示小Z进入的遗迹次数。
对于每次进入遗迹，第一行将给出一个整数k$$ (2≤k≤5)$$，表示传送门的个数。
接下来kk行，每行有两个整数$$x,y (1≤x≤n，1≤y≤m)$$，表示坐标(x,y)上有一个传送门。 数据保证传送门的坐标两两不同。
输出描述:
输出TT行，第i行表示第ii次进入该遗迹的宝藏的最大值。
示例1
3 3
1 2 3
4 5 6
7 8 9
2
2
1 1
3 3
3
1 1
1 3
3 1
输出
复制
58
41
题解
\[f[i][j]$$记录从终点到（i, j）的最大值
$$g[i][j]$$记录从起点到（i, j）的最大值
因为传送门只传送一次，且k的范围很小，可以直接遍历所有情况
最终结果是不使用传送门或者使用某个传送门的情况
```c++
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define SZ(v) ((int)v.size())
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef double db;
using namespace std;
const int N = 1e3+10;
int _;
int n, m, k;
int a[N][N];
ll f[N][N], g[N][N];
void solve() {
cin >> k;
vector<pair<int, int>> b;
for(int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
b.pb(make_pair(x, y));
}
ll ans = f[1][1];
for(int i = 0; i < k; i++) {
for(int j = 0; j < k; j++) {
if(i == j) continue;
ans = max(ans, f[b[i].fi][b[i].se] + g[b[j].fi][b[j].se]);
}
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// _ = 1;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
// f[i][j] 终点到(i，j)的最大值
memset(f, -0x3f, sizeof f);
f[n+1][m] = f[n][m+1] = 0;
for(int i = n; i >= 1; i--) {
for(int j = m; j >= 1; j--) {
f[i][j] = max(f[i+1][j], f[i][j+1]) + a[i][j];
}
}
// g[i][j] 起点到(i，j)的最大值
memset(g, -0x3f, sizeof g);
g[0][1] = g[1][0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
g[i][j] = max(g[i-1][j], g[i][j-1]) + a[i][j];
}
}
cin >> _;
while(_--) {
solve();
}
return 0;
}
```\]
标签：传送门,
探险,
int,
坐标,
宝藏,
遗迹,
define
From： https://www.cnblogs.com/zhyyyyy115/p/17421623.html