poj3181(Dollar Dayz)

 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

5 3

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\n", a[n]);
    return 0;
}