本蒟蒻想了一下午想不明白为什么不能直接加上 $|x-y|$ 每一位对应的二进制数的最小权值？为什么要费大力气搞DP？求大佬点拨。

回复必关注

附上蒟蒻 $27$ 分代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int T;
ll dp[36],a[36],inf=1e18;
/*
1
4 23 3
1 5 2 4
*/
ll work(ll z)//直接求每一位的最小值
{
	ll ans=0;
	int i=0;
	while(z)
	{
		if(z&1)
		{
			ans+=dp[i];
		}
		z>>=1;
		i++;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>T;
	while(T--)
	{
		memset(a,0x7f,sizeof a);
		memset(dp,0,sizeof dp);
		ll x,y;
		int k;
		cin>>x>>y>>k;
		for(int i=0;i<=k;i++)
		{
			cin>>a[i];
		}
		if(x==y)
		{
			cout<<0<<'\n';
			continue;
		}
		dp[0]=a[0];
		for(int i=1;i<=32;i++)
		{
			dp[i]=min(a[i],min(inf,dp[i-1]*2));//记录每一位权值
		}
		ll z=abs(x-y);
		ll ans=work(z);
		for(int i=0;i<=32;i++)
		{
			if((1ll<<i)>z)
			{
				ans=min(ans,min(inf,dp[i]+work((1ll<<i)-z)));//计算从大减到小的答案
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}