翻译(机翻)
2023-08-12 18:06:37
发布于:广东
贝西和朋友们被抓获,并被困在远离农场的一个秘密大院里,贝西必须计划他们的逃跑!该院落由 N K NK 个保持单元组成,排列成 N × K N×K 矩形网格,水平和垂直相邻单元之间有门。每个牢房恰好容纳一头牛。
贝西已经侵入了系统,并且能够解锁任何门的子集,但每个门都有成本。为了让奶牛逃脱,贝西必须打开足够多的门,让所有奶牛都可以聚集在一个牢房中(这样它们就有足够的奶牛力量来挖掘地表!)。Bessie 希望最小化总解锁成本。
但赌注比以往任何时候都更高,贝西不能满足于只有一个逃跑计划:她需要后援。帮她数数最低成本的逃跑计划有多少种;如果其中一个计划中的某些门需要解锁,而另一个计划中不需要解锁,则两个计划被视为不同。
由于这个数字可能非常大,因此仅输出其模 10 9 + 7 109+7的余数。
输入格式(文件 Escape.In):
第一行包含两个空格分隔的整数 N N 和 K K ( 2 ≤ N ≤ 30000 , 2 ≤ K ≤ 6 2≤N≤30000,2≤K≤6 )。接下来的 N N 行中的每一行都包含 K − 1 K−1 个 空格分隔的整数:解锁水平边缘上每个门的成本。
接下来的K K行中的每一行都 包含 N − 1 N−1 个 空格分隔的整数:解锁垂直边缘上每个门的成本。
所有费用均在 1 1 至 10 9 109之间 (含)。
在20%的测试用例中,保证 N ≤ 500 N≤500 ,并且所有权重在 1 1 和 5 5之间 (包括1 1 和5 5)。
在另外 20% 的测试用例中,保证 N ≤ 5000 N≤5000。
输出格式(文件 Escape.Out):
单个整数:最小成本逃生计划的数量,模 10 9 + 7 109+7。
样本输入:
4 3
1 1
5 6
7 8
1 1
1 1 1
2 3 4
1 1 1
样本输出:
10
测试用例呈现一个 4x3 网格,
1 1
+-----+-----+
| | |
1 | |2 | 1
| 5 | 6 |
+-----+-----+
| | |
1 | |3 | 1
| 7 | 8 |
+-----+-----+
| | |
1 | |4 | 1
| | |
+-----+-----+
1 1
任何最小成本逃生计划都会使用成本 2 的门口、成本 3 的门口以及成本 1 的大约 9 个门口。对于不使用成本 1 的边有 10 个选择,因此答案是 10。
全部评论 1
顶
2023-09-05 来自 广东
0
有帮助,赞一个