Description
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$1Write 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
题意：求1~m中的整数有多少种组成n的方法。
方法1：完全背包问题，注意高精度即可。
方法2：我用的是动态规划来拆分整数，想起来更容易些。设dp[n][m]表示用不超过m的整数表示n的方法数，分情况讨论：
m=0时，dp[n][0]=0；
m>n时，dp[n][m]=dp[n][n]；
0<m<=n时，若拆分出的整数最大是m，则方法数为dp[n-m][m]，若最大整数小于m，则方法数为dp[n][m-1]。所以总数为dp[n][m]=dp[n-m][m]+dp[n][m-1]。
空间还可以进一步优化，利用滚动数组，减去第二维。
最后就是注意高精度，将大数分割成两部分，右半部分属于long long范围内，左半部分除以1e18后另外保存，具体见代码。
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
typedef long long LL;
const LL MOD = 1e18;
LL a[1005], b[1005];
int main()
{
int n, m;
cin >> n >> m;
a[0] = 1;
for (int j = 1; j <= m; ++j)
for (int i = j; i <= n; ++i)
{
b[i] = b[i-j] + b[i] + (a[i-j] + a[i]) / MOD;
a[i] = (a[i-j] + a[i]) % MOD;
}
if (b[n])
printf("%lld", b[n]);
printf("%lld
", a[n]);
return 0;
}