题解：P11507 [ROIR 2017 Day 1] 计算器
bz029
·
·
题解
题目分析
有三个操作 A，B 和 C。n 分别需要操作 a，b 和 c 次，自由调整操作顺序，使最后 n 最小。
操作 A，使
操作 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 代码
```cpp
#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;
}
```
管理员大大求过！！！