Strange Bank（Atcoder初学者竞赛099）

Question

某银行为提高取款难度，只允许客户一次取款以下金额之一：

1 日元（日本货币）

6日元，6^2(=36)日元，6^3(=216)日元，...

9日元，9^2(=81)日元，9^3(=729)日元，...

一共至少需要多少次操作才能取出恰好N日元？

不允许再次存入您取出的钱。

约束条件 1≤N≤100000 N为整数。

输入来自标准输入，格式如下：

N 输出如果至少需要x次操作才能总共取出N日元，则打印x。

示例输入 1 127 示例输出 1 4个提取1日元、9日元、36(=6^2)日元、81(=9^2)日元，分四次操作可以提取127日元

对我来说这似乎是一个简单的贪心问题，所以这就是我使用的方法，但我看到其中一个样本得到了不同的结果并想通了，不会一直贪心。

#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <cmath>

using namespace std;


int intlog(int base, long int x) {
return (int)(log(x) / log(base));
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

long int n;cin>>n;

int result=0;
while(n>0)
{
int base_9=intlog(9,n);int base_6=intlog(6,n);
int val;
val=max(pow(9,base_9),pow(6,base_6));
//cout<<pow(9,base_9)<<" "<<pow(6,base_6)<<"\n";
val=max(val,1);
if(n<=14 && n>=12)
    val=6;
n-=val;
//cout<<n<<"\n";
result++;
}
cout<<result;
return 0;
}

在 n 14 和大于 12 时，我们必须选择 6 而不是 9，因为要达到零，将需要更少的步骤。

它只为 18/22 TC 提供 AC 请帮助我理解我的错误。

Answer 1

贪婪在这里不起作用，因为贪婪地选择答案，即每一步的最佳结果并不能保证最好的最终结果（你可以在你的例子中看到）。因此，您应该在每一步遍历所有可能的场景，以找出总体最优结果。

现在让我们看看如何做到这一点。如您所见，这里的最大输入可能是 10^5。并且我们可以在一次操作中取出以下仅有的12个值中的任意一个 -

[1, 6, 9, 36(=6^2), 81(=9^2), 216(=6^3), 729(=9^3), 1296(=6^4), 6561(=9^4), 7776(=6^5), 46656(=6^6), 59049(=9^5)]

因为6^7和9^6会大于100000

所以在每个值为 n 的步骤中，我们将尝试从上述数组中获取每个可能的（即小于或等于 n）元素 arr[i]，然后递归求解n-arr[i] 的子问题，直到我们达到零。

solve(n)
 if n==0 
  return 1;
 ans = n;
 for(int i=0;i<arr.length;i++)
   if (n>=arr[i])
     ans = min(ans, 1+solve(n-arr[i]);
 return ans;

现在这是非常耗时的递归解决方案(O(n*2^12))。我们将尝试优化它。当您尝试一些示例案例时，您会发现子问题是重叠的，这意味着可能存在重复的子问题。这就是动态规划的用武之地。您可以存储每个子问题的解决方案，以便我们将来可以重新使用它们。所以我们可以修改我们的解决方案如下

solve(n)
 if n==0 
  return 1; 
 ans = n;
 if(dp[n] is seen)
   return dp[n];
 for(int i=0;i<arr.length;i++)
   if (n>=arr[i])
     ans = min(ans, 1+solve(n-arr[i]);
 return dp[n] = ans;

DP求解的时间复杂度为O(n*12);

Strange Bank（Atcoder初学者竞赛099）

Strange Bank(Atcoder Beginner contest 099)

algorithm

math

greedy