P11507 [ROIR 2017 Day 1] 计算器
思路
简单的动态规划。
\(dp_{i,j,k}\) 表示使用了 \(i\) 次按钮 A，\(j\) 次按钮 B 和 \(k\) 次按钮 C。
转移式：
\[\begin{cases} dp_{i+1,j,k}=\min (dp_{i+1,j,k},\lfloor dp_{i,j,k}\div2\rfloor)； \\ dp_{i,j+1,k}=\min (dp_{i,j+1,k},\lfloor(dp_{i,j,k}+1)\div2\rfloor)； \\ dp_{i,j,k+1}=\min (dp_{i,j,k+1},\max (0,\lfloor(dp_{i,j,k}-1)\div2)\rfloor)； \end{cases} \]初始值：\(dp_{0,0,0}=n\)，其余为 \(INF\)。
答案：\(dp_{a,b,c}\)。
AC 代码
#include<bits/stdc++.h>
using namespace std;
#define N 105
long long n,a,b,c,dp[N][N][N];
int main(){
cin>>n>>a>>b>>c;
memset(dp,0x3f,sizeof(dp));
dp[0][0][0]=n;
for(int i=0;i<=a;i++){
for(int j=0;j<=b;j++){
for(int k=0;k<=c;k++){
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(0ll,(dp[i][j][k]-1)/2));
}
}
}
cout<<dp[a][b][c]<<endl;
return 0;
}