think 1遞推式完全背包 2題意提示可知如果3種都不買也算是一種方案，因此應該將dp[]數組全部初始化為1
sdut原題鏈接
高數Umaru系列（3）——喵星人 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 高數巨養了一只喵星人，作為一個負責任的鏟屎官，高數巨每天都會去給喵星人買新鮮的貓糧。超市里有3種貓糧，超市很大，每種貓糧都有無限袋，種類及價格如下： 土豪喵豪華版貓糧：12元/袋 小資喵樂享版貓糧：5元/袋 摳腳喵經濟版貓糧：2元/袋 高數巨帶了N元去超市買貓糧，對于某種貓糧她可以買0袋或多袋，只要總花費不超過N元就可以，那么她總共有多少種購買貓糧的方案？（PS：三種貓糧都不買也算是一種購買方案）
Input 多組輸入。 對于每組數據，只有一個整數N（ 1 < = N < = 200 ），代表高數巨帶的錢
Output 對于每組數據，輸出一個整數，代表高數巨可以購買貓糧的方案數，每組輸出占一行
Example Input 1 15 100
Example Output 1 20 1843
Hint
Author Shannon 以下為accepted代碼
#include <stdio.h>#include <string.h>int main(){ int n, i, j, c[] = {2, 5, 12}; int dp[204]; for(i = 0; i <= 204; i++) dp[i] = 1; for(i = 0; i < 3; i++) { for(j = c[i]; j <= 204; j++) { dp[j] = dp[j] + dp[j-c[i]]; } } while(scanf("%d", &n) != EOF) { printf("%d/n", dp[n]); } return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 104KBSubmit time: 2017-02-18 15:59:37****************************************************/新聞熱點
疑難解答
