钱币兑换问题_完全背包&&拆分&&母函数

ps：原来用新浪，可是代码的排版不是很好，所以用博客园啦，先容许我把从八月份开始的代码搬过来，从这里重新出发，希望这里可以一直见证我的成长。

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9186    Accepted Submission(s): 5591

Problem Description

在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

 

Input

每行只有一个正整数N，N小于32768。

 

Output

对应每个输入，输出兑换方法数。

 

Sample Input

2934
12553

 

Sample Output

718831
13137761

 

Author

SmallBeer(CML)

 

Source

杭电ACM集训队训练赛（VII）

 

完全背包：

#include<iostream>

using namespace std;

const int N=35000;

int a[N],b[N];

int main()

{

     int n;

    int  i,j,k;

        a[0]=1;

        for(i=1;i<=3;i++)

            for(j=i;j<=N;j++)

            {

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

            }

  while(cin>>n)

    {

        cout<<a[n]<<endl;

    }

    return 0;

}

　　拆分，先看能兑换多少三分的硬币，然后再加上两分的能换多少

#include<iostream>

using namespace std;

const int N=35000;

int a[N],b[N];

int main()

{

    int n;

     while(cin>>n)

     {

         int i;

         int k=n/3+1;//n/3是n中能换多少个3，就有多少种方法，加一是还有全部用1组成的情况

         for(i=0;i<=n/3;i++)//3分的数量从0开始遍历

         {

             int s=(n-3*i)/2;//2分的数量，除去当前三分的总额，还能有多少2分，就有多少情况；

             k+=s;

         }

         cout<<k<<endl;

     }

    return 0;

}

　　母函数模板直接套：

#include<iostream>

#include<string.h>

using namespace std;

const int N=35000;

int a[N],b[N];

int main()

{

    int i,j,n,k;

    for(i=0;i<N;i++)

        a[i]=1;

    memset(b,0,sizeof(b));

    for(i=2;i<=3;i++)

    {

        for(j=0;j<N;j++)

            for(k=0;k+j<N;k+=i)

            {

                b[j+k]+=a[j];

            }

            for(j=0;j<N;j++)

            {

                a[j]=b[j],b[j]=0;

            }

    }

    while(cin>>n) cout<<a[n]<<endl;

    return 0;

}