#P13008. 【MX-X13-T3】「KDOI-12」只有失去光明,才能逃脱黑暗。

    ID: 12719 Type: RemoteJudge 2000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 4 Uploaded By: Tags>动态规划 DP贪心O2优化位运算梦熊比赛

【MX-X13-T3】「KDOI-12」只有失去光明,才能逃脱黑暗。

题目描述

给定一个非负整数 xx,你要经过若干次以下操作将其变成 yy,求最小代价:

  • 选择一个 0ik0\leq i\leq k,花费 aia_i 代价将 xx 加或减 2i2^i

注意:你在操作时不需要保证 xx 为非负整数。

输入格式

本题有多组测试数据。

第一行,一个正整数 TT,表示测试数据组数。对于每组测试数据:

  • 第一行,三个非负整数 x,y,kx,y,k
  • 第二行,k+1k+1 个正整数 a0,,aka_0, \ldots, a_k

输出格式

对于每组测试数据,一行,一个非负整数,表示最小代价。

5
2 4 1
2 5
2 5 2
2 5 2
3 9 2
1 2 3
4 23 3
1 5 2 4
1 114 5
1 4 1 9 19 8
4
4
5
11
29

提示

【样例解释】

对于样例的第二组测试数据:经过以下两次操作即可让 xx 变为 yy,且代价最小:

  • i=2i=2,令 xx+22x\gets x+2^2,此时 x=6x=6,总代价为 22
  • i=0i=0,令 xx20x\gets x-2^0,此时 x=5x=5,总代价为 44

【数据范围】

本题使用捆绑测试。

子任务编号 分值 TT\leq x,y<x,y< kk\leq aia_i
11 66 10310^3 232^3 33 109\leq10^9
22 1515 2102^{10} 1010
33 2121 2×1052\times10^5 2302^{30} 11
44 2727 3030 2\leq2
55 2020 10410^4 109\leq10^9
66 1111 2×1052\times10^5

对于所有数据:1T2×1051\leq T\leq2\times10^50x,y<2300\leq x,y<2^{30}1k301\leq k\leq 301ai1091\leq a_i\leq10^9

【提示】

请使用较快的读入方式。