POJ 3181 Dollar Dayz && Uva 147 Dollars（完全背包）

时间：2023-03-08 15:55:36

　　首先是 Uva 147：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=83

　　细心看完这题后发现还是完全背包，只不过需要对浮点数处理一下。即把所有硬币的面值都乘以100，化为整数，对输入的数据也作同样的处理，然后就是套完全背包的模板了，在输出时还要用格式和精度来卡一卡你……一开始我没想到用printf可以的，于是百度了cout的输出格式控制，确实cout的格式和精度控制相比起printf来说都很不方便啊。。。

 #include<cstdio>

 #include<iomanip>

 #include<iostream>

 using namespace std;

 typedef long long LL;

 const LL coin[]= {,,,,,,,,,,,};

 LL f[]= {};

 inline void init(){

     for(LL i=; i<=; ++i)

         for(LL j=coin[i]; j<=; ++j)

             f[j]+= f[j-coin[i]];

 }

 int main(){

     init();

     double money;

     cout.setf(ios::fixed);

     cout.precision();

     while(cin>>money && money!=0.00){

         cout<<setw()<<money<<setw()<<f[int(money*+0.5)]<<endl;　　　　//这里的money转化为整数时要切记+0.5！防止精度误差！

     }

     return ;

 }

　　而用scanf和printf的话只需这么简洁即可：

 while(scanf("%lf",&money),money!=0.00){

     printf("%6.2f%17lld\n",money,f[int(money*+0.5)]);

 }

　　然后是 POJ 3181：http://poj.org/problem?id=3181

　　虽然还是用硬币作背景，但其实就是整数划分，一开始我数组开小了，结果RE了，后来开大数组后却忘记测试那些强力数据了，到看了别人的博客后才知道会超long long的，我就想难道要用高精度？可别人说直接高精度的话会TLE的，因为测试过最大的数据只是33位而已，所以用两个long long即可，同样式利用高精度的原理来进行加法模拟，要注意一些输出的细节即可：

 #include<cstdio>

 #include<cstring>

 typedef long long LL;

 const LL largest= 1e17;

 LL f1[], f2[];

 int main(){

     int n,k;

     while(~scanf("%d%d",&n,&k)){

         memset(f2,,sizeof(f2));

         memset(f1,,sizeof(f1));

         f2[]= ;

         for(int i=; i<=k; ++i)

             for(int j=i; j<=n; ++j){

                 f1[j]+= f1[j-i];

                 f2[j]+= f2[j-i];

                 if(f2[j]>=largest){

                     f1[j]+= f2[j]/largest;

                     f2[j]%= largest;

                 }

             }

         if(!f1[n])    printf("%I64d\n",f2[n]);

         else    printf("%I64d%017I64d\n",f1[n],f2[n]);

     }

     return ;

 }

　　附上kuangbin大神的精辟题解：http://www.cnblogs.com/kuangbin/archive/2012/09/20/2695165.html

相关文章