Dollar Dayz
Farmer John goes to Dollar Days at The Cow Store and discovers an unlimited number of tools on sale. During his first visit, the tools are selling variously for $1, $2, and $3. Farmer John has exactly $5 to spend. He can buy 5 tools at $1 each or 1 tool at $3 and an additional 1 tool at $2. Of course, there are other combinations for a total of 5 different ways FJ can spend all his money on tools. Here they are:
1 @ US$3 + 1 @ US$2
1 @ US$3 + 2 @ US$1
1 @ US$2 + 3 @ US$1
2 @ US$2 + 1 @ US$1
5 @ US$1
Write a program than will compute the number of ways FJ can spend N dollars (1 <= N <= 1000) at The Cow Store for tools on sale with a cost of $1..$K (1 <= K <= 100).
Input
A single line with two space-separated integers: N and K.
Output
A single line with a single integer that is the number of unique ways FJ can spend his money.
Sample Input
5 3
Sample Output
5
Source
题目类型：完全背包
算法分析：dp[i][j]表示使用前i种数字所能够组成的数字j的方案数，初始化dp[0][0] = 1，状态转移方程为dp[i][j] = dp[i-1][j] + dp[i][j-i]，由于最后的结果比较大，所以需要使用高精度计算，这里拼接两个long long长度的变量来存储结果。空间上还可以将第一维优化掉
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
/************************************************** filename :f.cpp author :maksyuki created time :2017/2/10 10:44:47 last modified :2017/2/10 16:56:26 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CPPFF ifstream cin ("in") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; LL dpa[1000+66], dpb[1000+66]; LL mod = (LL) 1e18; int main() { //CFF; //CPPFF; int N, K; scanf("%d%d", &N, &K); memset(dpa, 0, sizeof(dpa)); memset(dpb, 0, sizeof(dpb)); dpa[0] = 1; for(int i = 1; i <= K; i++) for(int j = 0; j <= N; j++) { if(j - i >= 0) { dpb[j] = (dpb[j] + dpb[j-i]) + (dpa[j] + dpa[j-i]) / mod; dpa[j] = (dpa[j] + dpa[j-i]) % mod; } } if(dpb[N]) printf("%I64d", dpb[N]); printf("%I64d\n", dpa[N]); return 0; } |
- « 上一篇：hdu1398
- poj2184：下一篇 »