这题和UVA 674差不多，都是硬币问题。上次我是抄的，结果还没看懂，这次终于自己写了！本来我已经想好了一种递推，用d[i][j]表示面值为 i 时必须用coin[j]且最大硬币为coin[j]时的总数，那么d[i][j] = d[i-coin[j]][0] + d[i-coin[j]][1] +……+d[i-coin[j]][j]，最终结果为d[i][0] + d[i][1] +……+d[i][10]，还是要有一个相加的过程，感觉不够利索，只好再重新构造递推关系，令f[i][j]表示面值为 i 时最大硬币为coin[j]时的总数，则f[i][j] = d[i][0] + d[i][1] +……+d[i][j]，f的递推关系为：f[i][j] = f[i-coin[j]][0] + f[i-coin[j]][1] +……+f[i-coin[j]][j]，看起来很简单，可是我推的时候却绕了老大弯子。最终结果就是f[i][10]了。在此吹下小牛，我感觉我写的比我抄的674那题要好。他的代码如下：
long dp(long s,long k)
{
if(d[s][k]!=-1) return d[s][k];
d[s][k]=0;
for(long i=k;i<6 && s>=coin[i];i++)
d[s][k]+=dp(s-coin[i],i);
//printf("d[%d][%d]:%d\n",s,k,d[s][k]);
return d[s][k];
}
如果把文中我加的一行输出中间过程的代码加上去，就会发现他的大部分dp[s-coin[i]][i]都是0，这对效率是种浪费。
这题和674还有些不一样，674数据都是整数，而这题是小数，很容易遇上浮点误差，不过用一些小技巧就能避免这个问题。
最后，我又花了一些时间来想边界问题，还算可以，只要memset一次就不需要再赋初值了。
1 #include<stdio.h>
2 #include<string.h>
3 typedef long long int llg;
4 llg f[6010][12];
5 int coin[] = {1,2,4,10,20,40,100,200,400,1000,2000};
6 llg dp(int i,int j)
7 {
8 llg &ans = f[i][j];
9 if(ans) return ans;
10 ans = 1;
11 for(int k = 1; k <= j && i >= coin[k]; k++)
12 ans += dp(i-coin[k],k);
13 return ans;
14 }
15 int main()
16 {
17 int a,b,sum;
18 llg ans;
19 memset(f,0,sizeof(f));
20 while(scanf("%d.%d",&a,&b)==2)
21 {
22 if(!a && !b) break;
23 sum = a*20 + b/5;
24 ans = dp(sum,10);
25 printf("%3d.%d%d%17lld\n",a,b/10,b%10,ans);
26 }
27 return 0;
28 }