POJ Dollar Dayz 美元假日（完全背包，常规+大数）

题意：给出整数n和k，n代表拥有的钱数量，k代表有k种工具，其价钱分别为1~k。求n元能有多少种购买的方案。

思路：k最大有100，数量过大，要用大数。其他的基本和完全背包一样。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int B=, N=;

 int coin[], n, k;

 struct bign {       //请先设置常数N作为缓冲区和最大整数的长度。

     int len, sex;

     int s[N];

     bign() {    //创建一个新的大数

         this -> len = ;

         this -> sex = ;

         memset(s, , sizeof(s));

     }

     bign (int number) {*this = number;}     //创建一个大数，用整型初始化

     bign (const char* number) {*this = number;} //创建一个大数，用字符串初始化

     void operator = (const char *number) {  //重载等号，等于一个字符串

         int begin = ;

         len = ;

         sex = ;

         if (number[begin] == '-') {

             sex = -;

             begin++;

         }

         else if (number[begin] == '+')

             begin++;

         for (int j = begin; number[j]; j++)

             s[len++] = number[j] - '';

     }

     bign operator = (int number) {          //重载等号，等于一个整型

         char str[N];        //注意这里的N，要设一个缓冲区在外面供使用。

         sprintf(str, "%d", number);

         *this = str;

         return *this;

     }

     bign change(bign cur) {

         bign now;

         now = cur;

         for (int i = ; i < cur.len; i++)

             now.s[i] = cur.s[cur.len - i - ];

         return now;

     }

     void delZore() {    // 删除前导0.

         bign now = change(*this);

         while (now.s[now.len - ] ==  && now.len > ) {

             now.len--;

         }

         *this = change(now);

     }

     void put() {    // 输出数值。

         delZore();

         if (sex <  && (len !=  || s[] != ))

             cout << "-";

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

             cout << s[i];

     }

     bign operator + (const bign &cur){      //只能是大数operator大数

         bign sum, a, b;

         sum.len = ;

         a = a.change(*this);

         b = b.change(cur);

         for (int i = , g = ; g || i < a.len || i < b.len; i++){

             int x = g;

             if (i < a.len) x += a.s[i];

             if (i < b.len) x += b.s[i];

             sum.s[sum.len++] = x % ;

             g = x / ;

         }

         return sum.change(sum);

     }

     bign operator - (const bign &cur) {     //只能是大数operator大数

         bign sum, a, b;

         sum.len = len;

         a = a.change(*this);

         b = b.change(cur);

         for (int i = ; i < b.len; i++) {

             sum.s[i] = a.s[i] - b.s[i] + sum.s[i];

             if (sum.s[i] < ) {

                 sum.s[i] += ;

                 sum.s[i + ]--;

             }

         }

         for (int i = b.len; i < a.len; i++) {

             sum.s[i] += a.s[i];

             if (sum.s[i] < ) {

                 sum.s[i] += ;

                 sum.s[i + ]--;

             }

         }

         return sum.change(sum);

     }

 };

 void cal()

 {

     dp[]=;

     for(int i=; i<=n; i++)  dp[i]=; //初始化

     int tmp=min(k,n);   //k>n的部分买不起

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

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

             dp[j+coin[i]] = dp[j+coin[i]] + dp[j];

     dp[n].put();

 }

 int main() {

     //freopen("input.txt", "r", stdin);

     for(int i=; i<; i++)    coin[i]=i+;    //初始化

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

         cal();

     return ;

 }

AC代码