#P18340. Sweet Sugar IV
Sweet Sugar IV
Sweet Sugar IV
标准输入,标准输出。
为了庆祝即将到来的儿童节,将举办一场收集糖果的游戏。游戏地图是一个 行 列的网格,行编号为 到 ,列编号为 到 。
地图中有 块糖。第 块糖位于格子 ,甜度为 。每个格子至多有一块糖。
有 个棋子,它们最初全部位于同一个格子 。每次操作,你可以选择一个棋子,将它从 移到 或 ;棋子不能移出地图。一个格子可以同时容纳多个棋子。
只要某个棋子位于一个有糖的格子上,你就会取得这块糖。每块糖只能被取得一次。特别地,如果起点有糖,它会立即被取得一次。
你可以进行任意多次合法操作,也可以随时停止。最终得分为取得的所有糖的甜度之和。
地图中还有 个矩形障碍。一个障碍用 表示,其中的所有格子都是危险格。棋子不能进入任何危险格。障碍满足以下保证:
- 地图边缘不会出现危险格,即 ,。
- 任意两个不同的障碍既不重叠,也不接触。这里的“接触”包括角接触:若两格满足 ,则它们视为相邻;相邻的两个危险格必须属于同一个障碍。
你会独立重玩这个游戏 次。每次重玩可以使用不同的起点 和棋子数 ;所有糖都会恢复。给定地图、糖和每次重玩的参数,请分别求出能够得到的最大得分。
输入格式
第一行包含五个整数 ,依次表示行数、列数、障碍数、糖的数量和重玩次数。
接下来 行,每行包含四个整数 ,表示一个闭矩形障碍。它覆盖的行号为 到 ,列号为 到 。
接下来 行,每行包含三个整数 ,表示一块糖的位置和甜度。糖的位置互不相同,且都是安全格。
接下来 行,每行包含三个整数 ,表示一次独立重玩的起点和棋子数。起点保证安全。
输出格式
输出 行,第 行包含一个整数,表示第 次重玩的最大得分。
数据范围
- ,;
- ;
- ,;
- 每个障碍满足 ,,不同障碍不重叠且不八方向接触;
- ,,;
- ,,。
输入只有一组地图;其中包含 次独立询问。
样例输入 1
3 3 1 4 5
2 2 2 2
1 1 1
3 3 1
1 2 3
2 1 5
1 1 1
1 1 2
1 3 2
1 2 2
2 1 1
样例输出 1
7
10
1
4
6
样例输入 2
5 7 1 3 4
2 3 3 4
3 1 1
2 2 10
5 4 100
1 2 1
1 2 2
1 1 2
2 7 1
样例输出 2
110
110
111
0
样例说明
第一组样例中,从 出发只用一个棋子,可以沿左侧绕过障碍,取得甜度为 的三块糖,得分为 。使用两个棋子时,可以分别沿障碍两侧移动,取得全部四块糖,总分为 。
第二组样例的最后一次重玩从 出发。棋子只能向下或向右移动,因此一块糖也取不到,答案为 。