小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,j的宝藏。
小Z会进入T次该遗迹。请你帮助小Z计算出，对于每次进入遗迹，在给定传送门的坐标的情况下，他在离开遗迹时所能获得的宝藏的价值的和最大为多少?
2869: 遗迹探险(线性DP)
时间限制: 2 Sec 内存限制: 256 MB提交: 0 解决: 18
[提交][状态][讨论版][命题人:]
题目描述
输入描述
第一行包含两个正整数n,m (2≤n≤103,2≤m≤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)上有一个传送门。数据保证传送门的坐标两两不同。
接下来有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次进入该遗迹的宝藏的最大值。
样例输入
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来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版