Смена монеты (значения монеты являются степенями м)

Внизу проблема была в конкурсе (теперь все кончено)
конкурс ссылка на сайт.

Кажется, вариант классической проблемы достоинства монет —
Дан массив (k элементов), имеющий значения монет и число n. Нам нужно ответить на количество способов сделать деноминацию n. мы можем решить это DP который займет O(n*k) время. Теперь в задаче конкурса вместо предоставления массива значений монет есть значение m, а значения монет — все возможные степени m ex. n= 200, m=3. поэтому у нас есть значения монет с [3^0, 3^1, 3^2, 3^3, 3^4]более высокие силы бесполезны для примера.

я использовал DP подход здесь, но это дает TLE, Видя ограничение по времени testcases<=10000, n<=10000, m<=10000Я предполагаю, что мы должны решить это для данного n,m в O(n) время [возможно, потребуется оптимизировать и этот. Пожалуйста, помогите мне решить эту проблему.
Мое решение с использованием DP,

#include <bits/stdc++.h>
#include <stdio.h>

using namespace std;

int solve(vector<int>&vec, int n){
cout<<"n= "<<n<<": m= "<<vec.size()<<endl;
int r=n+1, c=vec.size()+1;
vector<int>row(c,0);
vector<vector<int> >dp(r, row);
for(int i=0;i<c;i++)
dp[0][i]=1;
for(int i=1;i<r;i++){
for(int j=1;j<c;j++){
int a=0;
if(i-vec[j-1]>=0)
a=dp[i-vec[j-1]][j];
dp[i][j]=a+dp[i][j-1];
}
}
return dp[n][c-1];
}

int main()
{
ios::sync_with_stdio(false);
int tc,n,m;
cin>>tc;
while(tc--){
cin>>n>>m;
vector<int>temp;
int index=0;
temp.push_back(1);
while(temp[index]*m<=n){
temp.push_back(temp[index]*m);
index++;
}
int result=solve(temp,n);
cout<<result<<endl;
}
return 0;
}

2

Решение

«Смена монеты» и подобные проблемы с разделением обычно извлекают огромную выгоду из запоминания. Я не нашел никакого хитрого математического трюка, основанного на значениях степеней монеты, которые могли бы превзойти простой рекурсивный алгоритм с запоминанием.
этот ответ на связанный вопрос я проиллюстрировал влияние запоминания на алгоритм разделения более подробно)

Пример кода в Javascript ниже решает пример, где n,m = 200,3 в 0,026 мс, и сценарий наихудшего случая, когда n,m = 10000,2 в 2.8ms на моем рабочем столе i5; Я не знаю, каков был срок соревнования, но 10000 случайных случаев занимают около 3 секунд. И реализация C ++ будет, конечно, намного быстрее.

function coinPowers(n, m) {
if (n < 1 || m < 1) return 0;
if (n < m || m == 1) return 1;
var power = Math.floor(Math.log(n) / Math.log(m));
var memo = [];
for (var i = 0; i < n; i++) memo[i] = [];
return partition(n, m, power);

function partition(n, m, power) {
var count = memo[n - 1][power];
if (count) return count;
var coin = Math.pow(m, power), count = 1;
for (var p = power; p > 0; coin /= m, p--) {
if (coin < n) count += partition(n - coin, m, p)
else if (coin == n) ++count;
}
return (memo[n - 1][power] = count);
}
}

document.write(coinPowers(200, 3) + "<BR>");
document.write(coinPowers(200, 2) + "<BR>");
document.write(coinPowers(10000, 2) + "<BR>");
0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector