钱币兑换问题--hdu1284（完全背包）

Problem Description

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

Input

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

Output

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

Sample Input

2934

12553

Sample Output

718831

13137761

完全背包：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

using namespace std;

#define N 32770

int main()

{

    int i,j,n,v[]={,,,};

    int dp[N]={};

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

    {

        for(j=v[i];j<N;j++)

        {

            dp[j]+=dp[j-v[i]];

        }

    }

    while(scanf("%d",&n)!=EOF)

    {

        printf("%d\n",dp[n]);

    }

    return ;

}

#include<stdio.h>

#include<algorithm>

#include<string.h>

#define N 10

using namespace std;

int main()

{

    int n,s,i;

    while(scanf("%d",&n)!=EOF)

    {

        s=;

        for(i=;i<=n/;i++)

        {

            s+=(n-i*)/+;

        }

        printf("%d\n",s);

    }

    return ;

}

巴特西

钱币兑换问题--hdu1284（完全背包）

最新文章

热门文章