题目描述

题意很清晰明了不做赘述。

思路分析

取

d=|x-y|

，因为每次操作相当与在二进制的一位上加一，所以考虑将

d

按二进制进行数位 DP。

Solution

因为

a

数组可能有不优，所以先对它去除不优的元素

a_i=\min(a_{i-1}*2,a_i)

。
用

dp_{i,c}

表示已经处理完

i

位，再是否向

i+1

进位，具体转移见代码中。
可以发现只须要枚举到

d

的二进制位数加一即可，因为再往后不可能再产生更优解了。

Code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=40;
int a[N],dp[N][2];

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	for(;T--;)
	{
		int x,y,k;
		memset(a,127,sizeof a);
		memset(dp,63,sizeof dp);
		cin>>x>>y>>k;
		int d=abs(x-y),m=0;
		for(int i=d;i;m++) i>>=1;
		for(int i=0;i<=k;i++) cin>>a[i];
		for(int i=1;i<=m;i++) a[i]=min(a[i-1]<<1,a[i]);
		if(d&1) dp[0][0]=dp[0][1]=a[0];
		else dp[0][0]=0;
		for(int i=1;i<=m;i++)
		{
			if((d>>i)&1)
			{
				dp[i][0]=dp[i-1][0]+a[i];
				dp[i][1]=min(dp[i-1][1],dp[i-1][0]+a[i]);
			}
			else
			{
				dp[i][0]=min(dp[i-1][0],dp[i-1][1]+a[i]/*将这一位减一*/);
				dp[i][1]=dp[i-1][1]+a[i];
			}
		}
		cout<<dp[m][0]<<'\n';
	}
	return 0;
}

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

文章操作

题目描述

思路分析

Solution

Code

相关推荐

评论

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