下面的问题是在比赛中(现在已经结束了) 比赛link .
它似乎是经典硬币面额问题的变体 -
给定一个具有硬币值和数字 n 的数组(k 个元素)。我们需要回答有多少种方法可以确定 n 的面额。我们可以通过DP
来解决这需要 O(n*k)
时间。现在在竞赛问题中,不是给出硬币值数组,而是有一个值 m,硬币值是 m ex 的所有可能的幂。 n= 200, m=3.
所以我们有 [3^0, 3^1, 3^2, 3^3, 3^4]
的硬币值(value), 更高的权力对这个例子没有用]。
我用了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;
}
最佳答案
“硬币找零”和类似的分区问题通常会从内存中受益匪浅。我发现没有任何基于 m 次方硬币值的巧妙数学技巧可以击败带有内存的简单递归算法。
(在 this answer 的一个相关问题中,我更详细地说明了记忆化对分区算法的影响)
下面的 Javascript 代码示例在 0.026 毫秒内解决了 n,m = 200,3
的示例,以及 n,m = 10000,2
的最坏情况> 在我的 i5 桌面上为 2.8 毫秒;我不知道比赛的时间限制是什么,但是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>");
关于c++ - 硬币找零(硬币值(value)是 m 的幂),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33334043/