think: 1上午比賽自己一直卡在了這個題目上，自己一直在用遞推的方法找遞推方程，下午補題問身邊同學是要用遞推式完全背包來做，因為遞推的子問題是有序的，而這個題目其子問題是無序的，而且符合一種最優子結構 2題目需要特別注意的是提示了輸入數據超過了32000組，如果按照每個輸入數據都開始按照動態轉移方程重新計算更新的話會超時，因此建議開始輸入前將所有可能數據的情況統一計算，之后直接輸出對應的數據就行 3自己還有不明白的地方就是為什么這個題目要把dp[0] = 1， 但是如果不是把dp[0] = 1的話，按照dp[1] = 1, dp[2] = 2, dp[3] = 3的話就會有數據重復計算，自己用代碼嘗試了一下，發現后臺并沒有評判n = 0的情況，呃，這里是自己錯了，題目提示說了N是正整數，引以為戒，以后審題一定要細心
小P的故事——神奇的換零錢 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 已知A國經濟很落后，他們只有1、2、3元三種面值的硬幣，有一天小P要去A國旅行，想換一些零錢，小P很想知道將錢N兌換成硬幣有很多種兌法，但是可惜的是他的數學竟然是體育老師教的，所以他不會啊、、、他只好求助于你，你可以幫他解決嗎？ 提示：輸入數據大于32000組。
Input 每行只有一個正整數N，N小于32768。
Output 對應每個輸入，輸出兌換方法數。
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;}/* 判斷為遞推式完全背包的依據：遞推通常表現為子問題有序性，即子問題內順序不同即可認為方案不同，例如上臺階問題中先上一節臺階再上兩節臺階和先上兩節臺階再上一節臺階屬于不同方案，而在本題目，把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;}/* 判斷為遞推式完全背包的依據：遞推通常表現為子問題有序性，即子問題內順序不同即可認為方案不同，例如上臺階問題中先上一節臺階再上兩節臺階和先上兩節臺階再上一節臺階屬于不同方案，而在本題目，把3元錢先換給1元錢再換給2元錢，與把三元錢先換給2元錢再換給1元錢屬于同一方案*//***************************************************User name: Result: AcceptedTake time: 16msTake Memory: 260KBSubmit time: 2017-02-18 15:38:12****************************************************/以下為time limit exceeded——重復計算
#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;}/* 判斷為遞推式完全背包的依據：遞推通常表現為子問題有序性，即子問題內順序不同即可認為方案不同，例如上臺階問題中先上一節臺階再上兩節臺階和先上兩節臺階再上一節臺階屬于不同方案，而在本題目，把3元錢先換給1元錢再換給2元錢，與把三元錢先換給2元錢再換給1元錢屬于同一方案*//***************************************************User name: Result: Time Limit ExceededTake time: 1010msTake Memory: 0KBSubmit time: 2017-02-18 15:28:59****************************************************/新聞熱點
疑難解答
