「Bzoj 1655」「Usaco2006 Jan」 Dollar Dayz 奶牛商店 (背包DP+高精度)

BZOJ 1655
poj 3181
from: USACO 2006 Jan Sliver(USACO刷题第3题)

很容易看出本题是个无限背包方案数的dp，但是本题数据大会爆long long，那就可以把dp数组拆分为两个数组，类似于高精度压位地做

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;

const int MAXN = 1000 + 5;
const LL MOD = 1000000000000000000;

int k, n;
LL a[MAXN], b[MAXN];

void clear() {
    ms(a, 0), ms(b, 0);
}
void init() {
    clear();
    b[0] = 1;
}
void solve() {
    for (int i=1;i<=k;i++) {
        for (int j=i;j<=n;j++) {
            a[j] = a[j] + a[j-i] + (b[j] + b[j-i]) / MOD;
            b[j] = (b[j] + b[j-i]) % MOD;
        }
    }
    if (a[n]==0) printf("%lld\n", b[n]); else
    printf("%lld%018lld\n", a[n], b[n]);
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d%d", &n, &k)==2&&n&&k) init(), solve();
    return 0;
}