赞
踩
小Z是一名探险家。有一天,小Z误入了一个魔法遗迹。以下是该遗迹的具体组成:
1. 在 x 轴和 y 轴构成的平面上,满足在 1≤x≤n,1≤y≤m 的区域中(坐标(x,y)表示平面上的第x行的第y列),每个整数坐标 (x,y) 都有一个宝藏,坐标为(i,j)的宝藏的价值为ai,j(请注意,宝藏的价值可以为负)。换句话说,这个区域上的整点都有一个宝藏。
2. 对于任意一对点 (x1,y1) 和 (x2,y2),如果它们的横坐标相等,纵坐标之差为 1,则纵坐标小的点有一条道路可以到达纵坐标大的点,或者它们的纵坐标相等,横坐标之差为 1,则横坐标小的点有一条道路可以到达横坐标大的点。换句话说,(x,y)可以到达(x+1,y)或(x,y+1),反之不然。
3. 遗迹的入口在(1,1),出口在(n,m),小Z从入口进入后从出口离开,在移动的过程中他会将他所遇到的所有宝藏全部收集起来。
小Z想知道从进入到离开遗迹,他在离开遗迹时所能获得的宝藏的价值的和最大为多少。
作为一个有智慧的探险家,小Z当然会解决这个问题。但是由于这个遗迹具有魔法,问题就变得不是那么简单了。
在小Z进入该遗迹前,遗迹的魔法发动,它会在若干个具有宝藏的位置生成一个传送门。若小Z所在的坐标有传送门,则他可以通过这个传送门到达其它任意一个具有传送门的位置(当然,他也可以选择不使用传送门),并且小Z在使用一次传送门后,所有的传送门都会消失。换句话说,小Z只能最多使用一次传送门。
该遗迹具有魔法,每当小Z离开某个整点,该整点就会重新生成一个价值为ai,ja_{i,j}ai,j的宝藏。
小Z会进入TTT次该遗迹。请你帮助小Z计算出,对于每次进入遗迹,在给定传送门的坐标的情况下,他在离开遗迹时所能获得的宝藏的价值的和最大为多少?
第一行包含两个正整数 n,m (2≤n≤103),变量的含义如题意所示。 接下来有n行,每行有m个整数,其中第i行第j列的数字代表坐标(i,j)的宝藏的价值ai,j (∣ai,j∣≤109)。 接下来有一个数字T (1≤T≤103),表示小Z进入的遗迹次数。 对于每次进入遗迹,第一行将给出一个整数k (2≤k≤5),表示传送门的个数。 接下来k行,每行有两个整数x,y (1≤x≤n,1≤y≤m),表示坐标(x,y)上有一个传送门。 数据保证传送门的坐标两两不同。
输出T行,第i行表示第i次进入该遗迹的宝藏的最大值。
示例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
分析:
计算两次dp,第一次计算从(1,1)到(i,j)的最大价值,第二次计算从(n,m)到(i,j)的最大价值(即任何一个点到(n,m)的最大价值),可以发现进入传送门可以多走一段路,那么最大价值就是不用传送门走到(n,m)的最大价值f(n,m),走到传送门的价值加上传送后(i,j)到(n,m)的最大值f(i1,j1)+g(i2,j2)。l另外需要预处理,注意存在负数情况。
代码:
- #include <bits/stdc++.h>
-
- using namespace std;
-
- typedef pair<int,int> pii;
- typedef long long ll;
-
- const int N=1010;
-
- ll a[N][N];
- ll f[N][N];
- ll g[N][N];
-
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
-
- int n,m;
- cin>>n>>m;
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++)
- {
- cin>>a[i][j];
- }
- }
- memset(f,-0x3f,sizeof f);
- memset(g,-0x3f,sizeof g);
- f[0][1]=0;
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++)
- {
- f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
- }
- }
- g[n][m+1]=0;
- for(int i=n;i>=1;i--)
- {
- for(int j=m;j>=1;j--)
- {
- g[i][j]=max(g[i+1][j],g[i][j+1])+a[i][j];
- }
- }
- int t;
- cin>>t;
- while(t--)
- {
- vector<pii> d;
- int k;
- cin>>k;
- while(k--)
- {
- int x,y;
- cin>>x>>y;
- d.push_back({x,y});
- }
- ll ans=f[n][m];
- for(int i=0;i<(int)d.size();i++)
- {
- for(int j=0;j<(int)d.size();j++)
- {
- if(i==j) continue;
- int x1=d[i].first;
- int x2=d[j].first;
- int y1=d[i].second;
- int y2=d[j].second;
- ans=max(ans,f[x1][y1]+g[x2][y2]);
- }
- }
- cout<<ans<<'\n';
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。