自动搬运

查看原文

来自洛谷，原作者为

	bz029 ​11

搬运于2025-08-24 23:07:57，当前版本为作者最后更新于2025-01-05 15:49:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

有三个操作 A，B 和 C。$n$ 分别需要操作 $a$，$b$ 和 $c$ 次，自由调整操作顺序，使最后 $n$ 最小。

操作 A，使 $n=\left \lfloor \frac{n}{2} \right \rfloor$。

操作 B，使 $n=\left \lfloor \frac{n+1}{2} \right \rfloor$。

操作 C，使 $n=\max(0,\left \lfloor \frac{n-1}{2} \right \rfloor)$。

做题思路

这道题先看数据，$a$，$b$ 和 $c$ 不超过 60，如果使用 dfs 暴力，其时间复杂度为 $O(3^{a+b+c})$，达到了 $7 \times 10^{85}$ 级别，只能通过第 1 个子任务。从而我们要使用 dp 来优化递归的过程。

dp 需要存储以下几个信息：

用了 $i$ 次操作 A，用了 $j$ 次操作 B，用了 $k$ 次操作 C 时 $n$ 最小为多少。

由此我们可以推出以下几个状态转移方程：

操作 A：$dp_{i+1,j,k}=\left \lfloor \frac{dp_{i,j,k}}{2} \right \rfloor$。

操作 B：$dp_{i,j+1,k}=\left \lfloor \frac{dp_{i,j,k}+1}{2} \right \rfloor$。

操作 C：$dp_{i,j,k+1}=\max(0,\left \lfloor \frac{dp_{i,j,k}-1}{2} \right \rfloor)$。

初始化：$dp_{0,0,0}=0$，其余为无限大。

目标：$dp_{a,b,c}$。

dp 时间复杂度为：$O((a+b+c) \times a \times b \times c)$。由于 $a$，$b$，$c$ 同级，所以时间复杂度也为：$O(3\times a^4)$。

AC 代码

#include <bits/stdc++.h>
#define int long long //记得开long long,n<=1e18 
using namespace std;

int n,a,b,c,dp[70][70][70];

signed main(){
	cin>>n>>a>>b>>c;
	memset(dp,0x3f,sizeof dp);//初始化为无穷大 
	dp[0][0][0]=n;
	for(int t=1;t<=a+b+c;t++){//一共需要操作a+b+c次 
		for(int i=0;i<=a;i++){
			for(int j=0;j<=b;j++){
				for(int k=0;k<=c;k++){
					if(dp[i][j][k]==dp[65][65][65]) continue;//特判没有转移到的 
					dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]/2);
					dp[i][j+1][k]=min(dp[i][j+1][k],(dp[i][j][k]+1)/2);
					dp[i][j][k+1]=min(dp[i][j][k+1],max((dp[i][j][k]-1)/2,0ll));
				}
			}
		}
	}
	cout<<dp[a][b][c];
	
	return 0;
}

管理员大大求过！！！