Странный Банк (Конкурс начинающих Atcoder 099) - PullRequest
Новая
       7

Странный Банк (Конкурс начинающих Atcoder 099)

0 голосов
/ 10 июня 2018

Чтобы затруднить вывод денег, определенный банк позволяет своим клиентам снимать только одну из следующих сумм за одну операцию:

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, потому что для достижения нуля потребуется меньше шагов.

Он получил AC только для 18/22 TCs. Пожалуйста, помогите мне понять мою ошибку.

1 Ответ

0 голосов
/ 10 июня 2018

Жадность здесь не сработает, поскольку выбор ответа жадно, т. Е. Оптимальный результат на каждом шаге не гарантирует наилучшего конечного результата (вы можете видеть это на своем примере).Таким образом, вместо этого вы должны пройти через все возможные сценарии на каждом шаге, чтобы выяснить общий оптимальный результат.

Теперь посмотрим, как мы можем это сделать.Как вы можете видеть, здесь максимальный вход может быть 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);

...