BZOJ 4265 货币系统

今天比赛的时候做到的。题解写得很简单，但是感觉对于我这种蒟蒻还是很有思考的价值的。

题面（由于题面很短，就不概括了）：小Q当上了新的宇宙大总统，他现在准备重新设计一套货币系统。

这个货币系统要求一共有m张货币，并且将他们按照币值从小到大排好序以后，前一个货币币值乘上x等于后一个货币币值，x∈{2,3,4,5}，最小的币值为1。

小Q出门喜欢带总币值为n的钱，因为这是他的幸运数字，所以他希望设计出来的货币系统可以使得他带最少张数的货币。

数据范围：1≤n≤10^18 1≤k≤100

这道题（权限题），拿到的时候给人一种隐约的背包感。数据范围让小蒟蒻我想到DP+矩阵乘法/二分。然而这些都只是YY，我们仔细分析一下题面，可以先将其简（fu za）化为以下这个问题(k_i∈{2,3,4,5},a_i∈N*)：
n=1*(a₁+k₁*(a₂+k₂*(a₃+k₃*(a₄+k₄*a₅)))) 求出min(a1+a2+a3+a4+a5) (为了方便叙述，取m=5讨论)

这个还是比较好理解的。5个面值分别为1,k₁,k₁*k₂,k₁*k₂*k₃,k₁*k₂*k₃*k₄,5个面值各取a_1，a_2，a_3，a_4，a₅张，把这个式子拆开就可以证明其正确性。然后我们可以得到，a₂=(m-a₁)/k₂，后面的a_3，a_4，a₅也是同理。

然后到这里小蒟蒻卡了一下。

反着考虑。假设我们已经得到所有货币的面值，肯定是从大到小贪心地取。因为货币i 的一张等同于k_i-1张货币i-1 ，所以a_i-1<k_i-1。因此，我们可以枚举k_i，然后倒过来将n^· 对k_i的余数（也就是a_i）计入答案，再将n^·除以k_i得到下一个n^·，直到除的次数（即k）用完。

因此，我们可以得到下面这个会T的算法（也就是小蒟蒻考试的时候上交的算法）：

 1 #define ll long long
 2 ll n;
 3 int k;
 4 ll dfs(ll xz,int cs){//xz表示当前值,cs表示还剩多少次
 5     if(xz==0)return 0;
 6     if(cs==1)return xz; 
 7     ll mi=1e18,ans;
 8     for(ll i=2;i<=5;i++){
 9         ans=dfs(xz/i,cs-1)+xz%i;
10         if(ans<mi)mi=ans;
11     }
12     return mi;
13 }
14 int main(){
15     scanf("%lld%d",&n,&k);
16     printf("%lld",dfs(n,k));
17 }

然后我就T了……

T了……

事实上，只要用map记忆化就可以了……怎么说呢……被自己蠢到了……

AC代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 ll n;
 5 int k;
 6 map<ll,ll>m[105];
 7 ll dfs(ll xz,int cs){
 8     if(m[cs].count(xz))return m[cs][xz];
 9     if(xz==0)return 0;
10     if(cs==1)return xz; 
11     ll mi=1e18,ans;
12     for(ll i=2;i<=5;i++){
13         ans=dfs(xz/i,cs-1)+xz%i;
14         if(ans<mi)mi=ans;
15     }
16     return m[cs][xz]=mi;
17 }
18 int main(){
19     scanf("%lld%d",&n,&k);
20     printf("%lld",dfs(n,k));
21 }

以此篇博客为戒，多存套路，少犯智障错误。