题解：P13008 【MX-X13-T3】「KDOI-12」只有失去光明，才能逃脱黑暗。

题目描述

给定一个非负整数

x

，你要经过若干次以下操作将其变成

y

，求最小代价：

选择一个 $0 \le i \le k$ ，花费 $a_i$ 代价将 $x$ 加或减 $2^i$ 。

且操作时不需要保证

x

为非负整数。

算法思路

首先，令

d=\left|x-y \right|

，很显然，从

x

变成

y

的过程相当于从

0

变成

d

的过程。

加或减

2^i

代表什么意思？可以将转化为二进制来解决。设一个二进制数的最右边一位是第

0

位，右边第二位是第

1

位，以此类推。所以加或减

2^i

就代表一个二进制数的第

i

位加或减

1

。

题目说可以花费

a_i

代价将一个二进制数的第

i

位加或减

1

，但将第

i

位加或减

1

的最小代价是

a_i

吗？显然不是。可以设

mina_i

为将第

i

位加或减

1

的最小代价，进行递推。以下是递推公式：

mina_i=\begin{cases} a_i & i = 0 \\ \min(a_i,mina_{i-1} \times 2) & 1 \le i \le k \\ mina_{i-1} \times 2 & i > k \end{cases}

这个公式是怎么来的？

第 $0$ 位只能花费 $a_i$ 来加或减 $1$ 。
对于 $1 \ge i \ge k$ ，可以花费 $a_i$ ，也可以花费两个 $mina_{i-1}$ ，两种中选小的那一个。
对于 $i>k$ ，只能花费两个 $mina_{i-1}$ 得到。

这是求

mina_i

的代码：

CPP

mina[0] = a[0];
for (int i = 1; i <= k; i++)
    mina[i] = min(mina[i - 1] * 2, a[i]);
for (int i = k + 1; i <= 33; i++)
    mina[i] = mina[i - 1] * 2;

接下来有一个简单的思路，我们从低到高来枚举

d

的第

i

位，如果这位是

0

，那就跳过；如果是

1

，那就将答案加上

mina_i

。然而这个方法看似正确，但却存在问题，可以看样例中的第二个数据：

d=(11)_2,mina_0=2,mina_1=4,mina_2=2

最小代价位

4

，方法为先花费

2

个代价在第

0

位减

1

，这时数从

0

变为

-1

。再花费

2

个代价把它的第

2

位加

1

，让它变成

(11)_2

，一共花费

4

个代价。

这个错误是因为每一位可以加

1

或减

1

，且不用保证这个数在操作过程中是非负整数。

所以要改变思路，用 dp 来解决。我们要考虑是否向前进位。设

f(i+1,j)

为解决

d

的

0

到

i

位，向

i+1

为进位为

j

的最小代价。其中

j=0

代表不进位，

j=1

代表进位。

枚举

d

的第

i

位和进位

j

。设

d

的这一位是

u

若 $u+j$ 是偶数，则不用管，因为这一位加或减 $2k$ ，相当于下一位加或减 $k$ 。令 $f(i+1,(u+j)/2)=\min(f(i+1,(u+j)/2),f(i,j))$ 。
若 $u+j$ 是奇数，这一位既可以加 $1$ 也可以减 $1$ ，同上面一种情况，加或减更多也不用考虑。所以令 $f(i+1,0)=\min(f(i+1,0),f(i,j)+mina_i)$ ， $f(i+1,1)=\min(f(i+1,1),f(i,j)+mina_i)$ 。

dp 的代码：

CPP

int d = abs(x - y), cnt = 0;
for (int i = d; i; i /= 2, cnt++);
for (int i = 0; i <= cnt; i++) {
	int u = d >> i & 1;
	f[i + 1][0] = f[i + 1][1] = INF;
	for (int j = 0; j <= min(1, i); j++) {
		if (u + j & 1) {
			f[i + 1][0] = min(f[i + 1][0], f[i][j] + mina[i]);
			f[i + 1][1] = min(f[i + 1][1], f[i][j] + mina[i]);
		} else f[i + 1][u + j >> 1] = min(f[i + 1][u + j >> 1], f[i][j]);
	}
}

代码

CPP

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 40;
const LL INF = 1e18;

LL a[N], mina[N], f[N][2];

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		int x, y, k;
		scanf("%d%d%d", &x, &y, &k);
		for (int i = 0; i <= k; i++)
			scanf("%lld", &a[i]);
        // 求mina
		mina[0] = a[0];
		for (int i = 1; i <= k; i++)
			mina[i] = min(mina[i - 1] * 2, a[i]);
		for (int i = k + 1; i <= 35; i++)
			mina[i] = mina[i - 1] * 2;
        // dp
		int d = abs(x - y), cnt = 0;
		for (int i = d; i; i /= 2, cnt++);
		for (int i = 0; i <= cnt; i++) {
			int u = d >> i & 1;
            //初始化f
			f[i + 1][0] = f[i + 1][1] = INF;
			for (int j = 0; j <= min(1, i); j++) {
				if (u + j & 1) {
					f[i + 1][0] = min(f[i + 1][0], f[i][j] + mina[i]);
					f[i + 1][1] = min(f[i + 1][1], f[i][j] + mina[i]);
				} else f[i + 1][u + j >> 1] = min(f[i + 1][u + j >> 1], f[i][j]);
			}
		}
        // 输出
		printf("%lld\n", f[cnt + 1][0]);
	}
	return 0;
}

如果你觉得题解有帮助，请留一个小小的赞，谢谢！

题解：P13008 【MX-X13-T3】「KDOI-12」只有失去光明，才能逃脱黑暗。

文章操作

题目描述

算法思路

代码

相关推荐

评论

题解：P13008 【MX-X13-T3】「KDOI-12」只有失去光明，才能逃脱黑暗。