think: 1上午比賽自己一直卡在了這個題目上，自己一直在用遞推的方法找遞推方程，下午補(bǔ)題問身邊同學(xué)是要用遞推式完全背包來做，因為遞推的子問題是有序的，而這個題目其子問題是無序的，而且符合一種最優(yōu)子結(jié)構(gòu) 2題目需要特別注意的是提示了輸入數(shù)據(jù)超過了32000組，如果按照每個輸入數(shù)據(jù)都開始按照動態(tài)轉(zhuǎn)移方程重新計算更新的話會超時，因此建議開始輸入前將所有可能數(shù)據(jù)的情況統(tǒng)一計算，之后直接輸出對應(yīng)的數(shù)據(jù)就行 3自己還有不明白的地方就是為什么這個題目要把dp[0] = 1， 但是如果不是把dp[0] = 1的話，按照dp[1] = 1, dp[2] = 2, dp[3] = 3的話就會有數(shù)據(jù)重復(fù)計算，自己用代碼嘗試了一下，發(fā)現(xiàn)后臺并沒有評判n = 0的情況，呃，這里是自己錯了，題目提示說了N是正整數(shù)，引以為戒，以后審題一定要細(xì)心
小P的故事——神奇的換零錢 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 已知A國經(jīng)濟(jì)很落后，他們只有1、2、3元三種面值的硬幣，有一天小P要去A國旅行，想換一些零錢，小P很想知道將錢N兌換成硬幣有很多種兌法，但是可惜的是他的數(shù)學(xué)竟然是體育老師教的，所以他不會啊、、、他只好求助于你，你可以幫他解決嗎？ 提示：輸入數(shù)據(jù)大于32000組。
Input 每行只有一個正整數(shù)N，N小于32768。
Output 對應(yīng)每個輸入，輸出兌換方法數(shù)。
Example Input 100 1500
Example Output
884 188251
Hint
Author xfl
以下為accepted代碼——dp[0] = 1, n = 0輸出1
#include <stdio.h>#include <string.h>int main(){ int n, i, j, c[] = {1, 2, 3}; int dp[40000]; memset(dp, 0, sizeof(dp)); dp[0] = 1; for(i = 0; i < 3; i++) { for(j = c[i]; j <= 32768; j++) { dp[j] = dp[j] + dp[j-c[i]]; } } while(scanf("%d", &n) != EOF) { printf("%d/n", dp[n]); } return 0;}/* 判斷為遞推式完全背包的依據(jù)：遞推通常表現(xiàn)為子問題有序性，即子問題內(nèi)順序不同即可認(rèn)為方案不同，例如上臺階問題中先上一節(jié)臺階再上兩節(jié)臺階和先上兩節(jié)臺階再上一節(jié)臺階屬于不同方案，而在本題目，把3元錢先換給1元錢再換給2元錢，與把三元錢先換給2元錢再換給1元錢屬于同一方案*//***************************************************User name: Result: AcceptedTake time: 16msTake Memory: 256KBSubmit time: 2017-02-18 15:29:38****************************************************/以下為accepted代碼——n = 0輸出0
#include <stdio.h>#include <string.h>int main(){ int n, i, j, c[] = {1, 2, 3}; int dp[40000]; memset(dp, 0, sizeof(dp)); dp[0] = 1; for(i = 0; i < 3; i++) { for(j = c[i]; j <= 32768; j++) { dp[j] = dp[j] + dp[j-c[i]]; } } while(scanf("%d", &n) != EOF) { if(n != 0) printf("%d/n", dp[n]); else printf("0/n"); } return 0;}/* 判斷為遞推式完全背包的依據(jù)：遞推通常表現(xiàn)為子問題有序性，即子問題內(nèi)順序不同即可認(rèn)為方案不同，例如上臺階問題中先上一節(jié)臺階再上兩節(jié)臺階和先上兩節(jié)臺階再上一節(jié)臺階屬于不同方案，而在本題目，把3元錢先換給1元錢再換給2元錢，與把三元錢先換給2元錢再換給1元錢屬于同一方案*//***************************************************User name: Result: AcceptedTake time: 16msTake Memory: 260KBSubmit time: 2017-02-18 15:38:12****************************************************/以下為time limit exceeded——重復(fù)計算
#include <stdio.h>#include <string.h>int main(){ int n, i, j, c[] = {1, 2, 3}; int dp[40000]; /*memset(dp, 0, sizeof(dp)); dp[0] = 1; for(i = 0; i < 3; i++) { for(j = c[i]; j <= 32768; j++) { dp[j] = dp[j] + dp[j-c[i]]; } }*/ while(scanf("%d", &n) != EOF) { memset(dp, 0, sizeof(dp)); dp[0] = 1; for(i = 0; i < 3; i++) { for(j = c[i]; j <= n; j++) { dp[j] = dp[j] + dp[j-c[i]]; } } printf("%d/n", dp[n]); } return 0;}/* 判斷為遞推式完全背包的依據(jù)：遞推通常表現(xiàn)為子問題有序性，即子問題內(nèi)順序不同即可認(rèn)為方案不同，例如上臺階問題中先上一節(jié)臺階再上兩節(jié)臺階和先上兩節(jié)臺階再上一節(jié)臺階屬于不同方案，而在本題目，把3元錢先換給1元錢再換給2元錢，與把三元錢先換給2元錢再換給1元錢屬于同一方案*//***************************************************User name: Result: Time Limit ExceededTake time: 1010msTake Memory: 0KBSubmit time: 2017-02-18 15:28:59****************************************************/新聞熱點
疑難解答
