11220: 洛谷P11188 -「KDOI-10」商店砍价
[Creator : ]
Description
有一个正整数 $n$，保证其只由数字 $1\sim 9$ 构成。
你可以做任意多次如下操作：
- 选择 $n$ 的一个数位 $x$，花费 $v_x$ 的代价删除它，注意，此时 $n$ 的数位个数会减少 $1$，$n$ 的值也会发生相应的变化；
- 或者，花费 $n$ 的代价把剩余的所有数位删除。
求把整个数删除的最小代价。
你可以做任意多次如下操作：
- 选择 $n$ 的一个数位 $x$，花费 $v_x$ 的代价删除它，注意，此时 $n$ 的数位个数会减少 $1$，$n$ 的值也会发生相应的变化；
- 或者，花费 $n$ 的代价把剩余的所有数位删除。
求把整个数删除的最小代价。
Input
本题有多组测试数据。
输入的第一行包含一个正整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。
第二行包含一个正整数 $t$，表示测试数据组数。
对于每组测试数据：
- 第一行一个正整数 $n$，表示这个数的初始值。
- 第二行九个正整数 $v_1,v_2,\dots,v_9$，表示删除每个数位的代价。
输入的第一行包含一个正整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。
第二行包含一个正整数 $t$，表示测试数据组数。
对于每组测试数据：
- 第一行一个正整数 $n$，表示这个数的初始值。
- 第二行九个正整数 $v_1,v_2,\dots,v_9$，表示删除每个数位的代价。
Output
对于每组测试数据：
- 输出一行一个正整数，表示最小代价。
- 输出一行一个正整数，表示最小代价。
Constraints
对于全部的测试数据，保证：
- $1\le t\le 10$；
- $1\le n< 10^{10^5}$；
- 对于任意 $1\le i\le 9$，$1\le v_i\le 10^5$；
- $n$ 由数字 $1\sim 9$ 构成。
- $1\le t\le 10$；
- $1\le n< 10^{10^5}$；
- 对于任意 $1\le i\le 9$，$1\le v_i\le 10^5$；
- $n$ 由数字 $1\sim 9$ 构成。
Sample 1 Input
0
3
123
10 10 10 10 10 10 10 10 10
1121
2 1 2 2 2 2 2 2 2
987654321
1 2 3 4 5 6 7 8 9
Sample 1 Output
21
6
45
对于第一组测试数据，最优操作方案如下：
- 删除数位 $2$，代价为 $10$，此时 $n$ 变为 $13$；
- 删除数位 $3$，代价为 $10$，此时 $n$ 变为 $1$；
- 删除 $n$ 的剩余所有数位，代价为 $1$。
总代价为 $10+10+1=21$，可以证明，这是代价的最小值。
对于第二组测试数据，一种最优操作方案如下：
- 删除第一个数位 $1$，代价为 $2$，此时 $n$ 变为 $121$；
- 删除最后一个数位 $1$，代价为 $2$，此时 $n$ 变为 $12$；
- 删除数位 $2$，代价为 $1$，此时 $n$ 变为 $1$；
- 删除 $n$ 的剩余所有数位，代价为 $1$。
总代价为 $2+2+1+1=6$。
- 删除数位 $2$，代价为 $10$，此时 $n$ 变为 $13$；
- 删除数位 $3$，代价为 $10$，此时 $n$ 变为 $1$；
- 删除 $n$ 的剩余所有数位，代价为 $1$。
总代价为 $10+10+1=21$，可以证明，这是代价的最小值。
对于第二组测试数据，一种最优操作方案如下：
- 删除第一个数位 $1$，代价为 $2$，此时 $n$ 变为 $121$；
- 删除最后一个数位 $1$，代价为 $2$，此时 $n$ 变为 $12$；
- 删除数位 $2$，代价为 $1$，此时 $n$ 变为 $1$；
- 删除 $n$ 的剩余所有数位，代价为 $1$。
总代价为 $2+2+1+1=6$。