#P16411. 旅行团行程收益

旅行团行程收益

假期旅行团(Vacation Tours)

题目背景

一家旅行社正在为一群住在同一家酒店的游客安排观光旅行。

每次旅行都会从酒店出发,游览若干景点后再回到酒店。为了避免游客重复参观同一个地方,不同旅行之间不能包含相同的景点。

旅行社每组织一次旅行,都会向整个旅行团收取一笔固定费用。与此同时,旅行社还需要承担酒店与景点之间、以及不同景点之间的交通费用。

请帮助旅行社安排若干次旅行,使最终收益最大。

题目描述

共有 NN 个地点,编号为:

0,1,…,N−1.0,1,\ldots,N-1.

其中:

  • 地点 00 是酒店;
  • 地点 11 到 N−1N-1 是景点。

一次旅行由一个非空的景点序列:

v1,v2,…,vkv_1,v_2,\ldots,v_k

构成,并按照以下路线行进:

0→v1→v2→⋯→vk→0.0\to v_1\to v_2\to\cdots\to v_k\to 0.

一次旅行中的景点必须两两不同。

旅行社可以安排任意多次旅行,也可以一次旅行都不安排。所有被安排的旅行还必须满足:

  • 每个景点至多出现在一次旅行中。

也就是说,游客不能在不同旅行中重复参观同一个景点。并不要求所有景点都必须被参观。

每安排一次旅行,旅行社都会收取固定费用 fee。

交通是有向的。从地点 ii 到地点 jj 的费用记为:

costi,j.cost_{i,j}.

通常情况下:

costi,j≠costj,i.cost_{i,j}\ne cost_{j,i}.

此外,交通费用不保证满足三角不等式。当路线要求从地点 ii 前往地点 jj 时,必须直接支付 costi,jcost_{i,j},即使经过其他地点会更加便宜,也不能用间接路线代替。

若一次旅行依次游览 v1,v2,…,vkv_1,v_2,\ldots,v_k,则其交通成本为:

$$cost_{0,v_1} +\sum_{i=1}^{k-1}cost_{v_i,v_{i+1}} +cost_{v_k,0}.$$

设一共安排了 rr 次旅行,所有旅行的交通成本之和为 CC,则旅行社的收益为:

r×fee−C.r\times fee-C.

请计算旅行社能够获得的最大收益。

由于可以选择不安排任何旅行,因此答案至少为 00。

交通费用的编码方式

交通费用使用两个 Base64 字符进行编码。

输入给出两个 N×NN\times N 的字符矩阵 cc 和 dd。从地点 ii 到地点 jj 的交通费用为:

$$cost_{i,j}=value(c_{i,j})\times 64+value(d_{i,j}).$$

字符对应的数值如下:

字符范围 数值
A 到 Z 00 到 2525
a 到 z 2626 到 5151
0 到 9 5252 到 6161
+ 6262
/ 6363

例如:

  • A 的值为 00;
  • B 的值为 11;
  • a 的值为 2626;
  • 0 的值为 5252;
  • / 的值为 6363。

若某项的两个编码字符分别为 B 和 J,则对应费用为:

1×64+9=73.1\times64+9=73.

输入格式

第一行包含两个整数 NN 和 fee,分别表示地点总数和每次旅行收取的固定费用。

接下来 NN 行,每行包含一个长度为 NN 的字符串,依次描述矩阵 cc。

随后 NN 行,每行包含一个长度为 NN 的字符串,依次描述矩阵 dd。

字符串中的字符均为题目规定的 Base64 编码字符。

输出格式

输出一个整数,表示旅行社能够获得的最大收益。

数据范围

对于所有测试数据:

  • 2≤N≤502\le N\le 50;
  • 1≤fee≤100001\le fee\le 10000;
  • 矩阵 cc 和 dd 均有 NN 行;
  • 每一行的长度均为 NN;
  • 所有字符均属于:
    • A 到 Z;
    • a 到 z;
    • 0 到 9;
    • +;
    • /;
  • 对于所有 0≤i<N0\le i<N,ci,ic_{i,i} 和 di,id_{i,i} 均为 A。

样例 1

输入

3 15
AAA
AAA
AAA
ABJ
JAB
BJA

输出

12

解释

解码后的交通费用矩阵为:

- 1 9
9 - 1
1 9 -

一种方案是分别安排只参观景点 11 和景点 22 的两次旅行。

两次旅行的成本均为 1010,总收费为:

15×2=30,15\times2=30,

因此收益为:

30−20=10.30-20=10.

更优的方案是只安排一次旅行:

0→1→2→0.0\to1\to2\to0.

其交通成本为:

1+1+1=3,1+1+1=3,

因此收益为:

15−3=12.15-3=12.

样例 2

输入

4 100
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA

输出

300

解释

所有交通费用均为 00。

分别为三个景点各安排一次旅行,可以安排 33 次旅行并获得:

3×100=3003\times100=300

的收益。

样例 3

输入

3 1000
A//
/A/
//A
A//
/A/
//A

输出

0

解释

所有可能的旅行成本都过高,因此最优方案是不安排任何旅行。

样例 4

输入

7 1000
AAA////
/AA/A//
//AA/A/
A//AA//
///AAA/
///A/AA
AA////A
AKo////
/AU/X//
//AZ/o/
j//AK//
///XAo/
///y/AK
KP////A

输出

1809

样例 5

输入

2 1
AA
AA
AA
AA

输出

1