Bzoj 1655(背包DP+高精度)

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

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

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
#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;
}
------ 本文结束 ------