3233: [Ahoi2013]找硬币
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 924 Solved: 482
[Submit][Status][Discuss]
Description
Input
Output
一行，一个整数，表示最少付的钱币数。
Sample Input
Sample Output
HINT
样例解释：共有两只兔纸，价钱分别为25和102。现在小蛇构造1，25，100这样一组硬币序列，那么付第一只兔纸只需要一个面值为25的硬币，第二只兔纸需要一个面值为100的硬币和两个面值为1的硬币，总共两只兔纸需要付4个硬币。这也是所有方案中最少所需要付的硬币数。
1<=N<=50, 1<=ai<=100,000
分析：
本来凑面值的题就是十分亲民的题，再加上数据又十分亲民，所以就是一道十分亲民的题……。
定义状态f[i]表示最大硬币为i面值时的最少硬币。转移方程f[i] = min（f[i]，f[j] - sum（（a[k] / i）* （i / j - 1）））；（j为i的因子，k为每只兔子价格）
为什么这么转移，因为比如说我们有三枚三元硬币，我们可以转换成一枚九元硬币。
很简单，比如说我们有一只兔子价格为28,用1元硬币去凑会用28枚（即f[1] = 28），用1、3去凑会有 f[3] = f[1] - 28 / 3 * （3 / 1 - 1） = 10枚硬币，用1,3，9去凑会有f[9] = f[3] - 28 / 9 * （9 / 3 - 1） = 4枚硬币。
其实转移是很简单的，但是发现i的范围是100,000 ，j是i的因子需要去转化，k是每只兔子，复杂度很高的。我们可以考虑省掉j。即我们用递推。
可以由f[j]倒推f[i]。
发现100000 内每个数 不停加本身，推到100000，再乘上50只兔子的复杂度才几千万，随便卡过。
我一开始是这么做的，于是4.6S过了（数据太亲民了）。
其实后面我想了一下还可以优化，因为比如说f[27]由f[9]推过去肯定比由f[3]推过去优，所以对于每个数我们只用去推它的质数倍数就好了。
设M =100,000,N = 50；
K 为 M内所有数乘以质数倍推到100000的复杂度（好像这个数才十万左右....）
筛素数（M loglog M），递推（N * K）所以复杂度是（M log log M + N * K）。然后就从4.6S降到了1.6S。话说数据是真亲民啊……
附上AC代码：
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
const int N = ;
const int M = 1e5 + ;
int a[N],n;
int f[M],ans,sum,maxn,cnt,p[M];
bool vis[M];
void shai(){
for(int i = ;i < M;i++){
if(!vis[i])p[++cnt] = i;
for(int j = ;j <= cnt;j++){
if(p[j] * i >= M)break;
vis[p[j] * i] = true;
if(i % p[j] == )break;
}
}
}
void Init(){
memset(f,0x3f3f3f3f,sizeof f);
}
int dp(int i,int j){
int ans = f[j];
for(int k = ;k <= n;k++){
ans -= (a[k] / i) * (i / j - );
}
return ans;
}
int main(){
Init(); scanf("%d",&n);
for(int i = ;i <= n;i++){
scanf("%d",&a[i]);sum += a[i];
maxn = max(maxn,a[i]);
}
f[] = sum;ans = f[];
for(int i = ;i <= maxn;i++){
f[i] = min(f[i],dp(i,));
ans = min(ans,f[i]);
}
shai();
for(int i = ;i <= maxn;i++){
for(int j = ;j <= cnt;j++){
if(p[j] * i > maxn)break;
f[p[j] * i] = min(f[p[j] * i],dp(p[j] * i,i));
ans = min(ans,f[p[j] * i]);
}
}
printf("%d\n",ans);
}