程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 1284 錢幣兌換問題 完全背包之方案總數~

hdu 1284 錢幣兌換問題 完全背包之方案總數~

編輯:關於C++

錢幣兌換問題

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


Problem Description 在一個國家僅有1分,2分,3分硬幣,將錢N兌換成硬幣有很多種兌法。請你編程序計算出共有多少種兌法。
Input 每行只有一個正整數N,N小於32768。
Output 對應每個輸入,輸出兌換方法數。
Sample Input
2934
12553

Sample Output
718831
13137761

狀態轉移方程:dp[i][j] = dp[i-1][j]+dp[1][j-(1~3)] (d[0][0] = 1);
代碼:
#include 
#include 
#define MAX 35000
int dp[MAX] ;
int main()
{
	int n;
	while(scanf("%d",&n) != EOF)
	{
		memset(dp,0,sizeof(int)*(n+10)) ;
		dp[0] = 1 ;
		for(int i = 1 ; i <= 3 ; ++i)
		{
			for(int j = i ; j <= n ; ++j)
				dp[j] = dp[j]+dp[j-i] ;
		}
		printf("%d\n",dp[n]) ;
	}
	return 0 ;
}

呵呵,,再附送你們一個神代碼(不是我寫的):
#include
int main()
{
    int n,sum,i;
    while(scanf("%d",&n)!=EOF)
    {
        int t=n/3+1;//3分的個數 
        sum=0;
        for(i=0;i
因為本題的錢幣數只有1,2,3三種,所以令t=n/3,然後遍歷一遍i從0到t,代表面值為三分的個數,然後用總價值減去三分硬幣所代表的價值,用這個值除以2,得到的數就是每確定一個三分的數值後對應的2分的硬幣的兌換總數。最後再加上全部為1分的情況,就是所求的解了。

下面的代碼簡直是碉堡了。
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved