D. Equalization

Problem - D - Codeforces

题意

给你两个数x,y。用x,y不断除以$2^k$，向下取整。每一个k都不同，最终x=y；操作的代价为$2^k$总和，求最小代价。

思路

首先，需要了解一个性质：

对于正整数 ( a ) 和 ( b )，以及任意实数 ( x )，有 ( $\lfloor \frac{\lfloor \frac{x}{C^a}\rfloor }{C^b}\rfloor =\lfloor \frac{x}{C^{a+b}}\rfloor$ )。这个性质表明，多次取整和除以 C 的幂次方的操作可以合并为一次操作。

可以从c进制入手证明。

为了代价最小，我们将k1,k2分解，找到最小代价。

因为2^5= 2^3 * 2^2> 2^2 + 2^3

所以，这是一个关于最小代价的动态规划问题。代码的目的是计算从起点 (0, 0) 到达某个点 (i, j) 的最小代价

代码分析

1. 初始化：
   • dp[i][j] = INF：将所有点的代价初始化为无穷大。
   • dp[0][0] = 0：起点的代价为0。
2. 动态规划填表：
   • 外层循环 x 从0到l-1，表示增加的步长。
   • 内层两个循环 i 和 j 分别从l-1到0逆序遍历。
   • dp[i+x][j] = min(dp[i+x][j], dp[i][j] + (1ll << x))：表示从点 (i, j) 水平移动 x 步到 (i+x, j) 的代价。
   • dp[i][j+x] = min(dp[i][j+x], dp[i][j] + (1ll << x))：表示从点 (i, j) 垂直移动 x 步到 (i, j+x) 的代价。
3. 查询最小代价：
   • 读取测试案例数量 t。
   • 对于每个测试案例，读取 x 和 y。
   • 遍历所有点 (i, j)，如果 (x >> i) == (y >> j)，则更新答案 ans 为 min(ans, dp[i][j])。
   • 输出最小代价 ans。

为什么逆序循环数组？

• 避免重复计算：如果正序遍历，那么在计算 dp[i+x][j] 时，dp[i][j] 可能已经被更新为本次迭代的结果，这会导致计算错误。
• 保证状态转移的正确性：逆序遍历可以确保在计算 dp[i+x][j] 和 dp[i][j+x] 时，dp[i][j] 是基于上一次迭代的结果，从而保证状态转移的正确性。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[100][100],l=60,INF=1e8;
signed main()
{
   for(int i=0;i<l;i++)
   for(int j=0;j<l;j++)
	dp[i][j]=INF;
	dp[0][0]=0;
	for(int x=0;x<l;x++)
	for(int i=l;i>=0;i--)
	for(int j=l;j>=0;j--)
	{
		dp[i+x][j]=min(dp[i+x][j],dp[i][j]+(1ll<<x));
		dp[i][j+x]=min(dp[i][j+x],dp[i][j]+(1ll<<x));
	}
	int x,y,t;
	cin>>t;
	while(t--)
	{
		int ans=INF;
		cin>>x>>y;
		for(int i=0;i<l;i++)
		for(int j=0;j<l;j++)
		{
			if((x >> i)==(y >> j))
			ans=min(ans,dp[i][j]);
		}
		cout<<ans<<'\n';
	}	 
}