#5：你的背包——6

自然数拆分，完全背包

#include <cstdio>
#define ll long long
#define mod 2147483648
#define rep(i, a, b) for (int i = a; i <= b; i++)

int n;
ll f[4005];

int main() {
    scanf("%d", &n);
    f[0] = 1;
    rep(i, 1, n)
        rep(j, i, n)
            f[j] = (f[j] + f[j-i]) % mod;
    printf("%d", (f[n]-1+mod) % mod);
    return 0;
}

POJ1015，自己实现果然要费时调试……按照题面对数据处理一下再背包。打印路径。

#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
#define R(a) scanf("%d", &a)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define irep(i, a, b) for (int i = a; i >= b; i--)
#define init(a, b) memset(a, b, sizeof(a))

const int maxn = 205;
int n, m, kase;
int a[maxn], b[maxn], t[maxn];
int f[25][850], d[25][850];
map<int, int> pre;
int ans[maxn], p, val1, val2;

void print(int j, int k, int i) {
    ans[++p] = i;
    val1 += a[i];
    val2 += b[i];
    int nxt = pre[i*1000000+j*10000+k];
    if (!nxt)    return;
    print(j-1, k-t[i], nxt);
}

int cmp(int a, int b) {
    int t = f[m][a], p = f[m][b];
    if (t < 0 && p < 0)    return -1;
    if (t >= 0 && p >= 0)    return t > p ? a : b;
    if (t >= 0)    return a;
    return b;
}

int main() {
    while (~scanf("%d%d", &n, &m) && n | m) {
        rep(i, 1, n) {
            R(a[i]);
            R(b[i]);
            t[i] = a[i] - b[i] + 20;
        }

        init(f, 0xcf);
        f[0][0] = 0;
        rep(i, 1, n)
            irep(j, m, 1)
                rep(k, t[i], 40*m) {
                    if (f[j-1][k-t[i]] >= 0 && f[j][k] < f[j-1][k-t[i]] + a[i] + b[i]) {
                        f[j][k] = f[j-1][k-t[i]] + a[i] + b[i];
                        pre[i*1000000+j*10000+k] = d[j-1][k-t[i]];
                        d[j][k] = i;
                    }
                }

        rep(i, 0, 20*m) {
            int k = cmp(20*m-i, 20*m+i);
            if (k >= 0) {
                p = val1 = val2 = 0;
                print(m, k, d[m][k]);
                break;
            }
        }
            
        printf("Jury #%d
Best jury has value %d for prosecution and value %d for defence:
", ++kase, val1, val2);    
        irep(i, p, 1)    printf(" %d", ans[i]);
        puts("
");
    }
    return 0;
}

POJ1742，按多重背包的思路贪心一下。

#include <cstdio>
#include <cstring>
#define maxm 100005
#define init(a, b) memset(a, b, sizeof(a))
#define R(a) scanf("%d", &a)
#define W(a) printf("%d
", a)
#define rep(i, a, b) for (int i = a; i <= b; i++)

int n, m;
int a[101], c[101];
int used[maxm];
bool f[maxm];

int main() {
    while (R(n), R(m), n) {
        init(f, 0);
        f[0] = true;
        rep(i, 1, n)    R(a[i]);
        rep(i, 1, n)    R(c[i]);
        rep(i, 1, n) {
            rep(j, 0, m)    used[j] = 0;
            rep(j, a[i], m) {
                if (!f[j] && f[j-a[i]] && used[j-a[i]] < c[i]) {
                    f[j] = true;
                    used[j] = used[j-a[i]] + 1;
                }
            }
        }

        int ans = 0;
        rep(i, 1, m)    ans += f[i];
        W(ans);
    }
    return 0;
}

BZOJ2287，退背包，可行方案数可以等于总数减去不可行方案数。

#include <bits/stdc++.h>
using namespace std;
#define R(a) scanf("%d", &a)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define irep(i, a, b) for (int i = a; i >= b; i--)

int n, m;
int w[2005];
int f[2005], g[2005];

int main() {
    R(n), R(m);
    f[0] = 1;
    rep(i, 1, n) {
        R(w[i]);
        irep(j, m, 0)
            f[j] = (f[j] + f[j-w[i]]) % 10;
    }

    rep(i, 1, n) {
        rep(j, 0, w[i]-1)    g[j] = f[j];
        rep(j, w[i], m)    g[j] = (f[j] - g[j-w[i]] + 10) % 10;
        rep(j, 1, m)    printf("%d", g[j]);
        puts("");
    }
    return 0;
}

BZOJ1025，把题目本质抽出来即和为n的拆分，然后难的一点是lcm方案数等价于各素数加和小于等于n的方案数。之后分组背包即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n;
ll f[1001];
int primes[1001], t;
bool mark[1001];

inline void Get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!mark[i]) {
            primes[++t] = i;
        }
        for (int j = 1; j <= t && i*primes[j] <= n; j++) {
            mark[i*primes[j]] = true;
            if (i % primes[j] == 0)    break;
        }
    }
}

inline ll dp(int n) {
    f[0] = 1ll;
    for (int i = 1; i <= t; i++)
        for (int j = n; j >= primes[i]; j--)
            for (int k = primes[i]; k <= j; k *= primes[i])
                f[j] += f[j-k];
    return accumulate(f, f+n+1, 0ll);
}

int main() {
    scanf("%d", &n);
    Get_primes(n);
    printf("%lld", dp(n));
    return 0;
}

BZOJ4247，首先排序，之后才能dp。dp的状态转移不是单纯的01背包因为那样会T，一种写法是处理一下使得大于n的状态都归于n；我用的第二种但私以为网上题解在理解上有些错误。一是这样写以后f[i][j]的定义其实变了，不再是前i个剩j个挂钩而是剩>=j个挂钩；二是选择1个的原因不是只能选1，而是我们本来要取1~n里最大的，而这种写法前面的一定比后面的大所以取1就能保证正确性了。果然最后的输出也不必把f数组遍历一遍，因为0肯定是最大的，直接输出即可AC。

#include <bits/stdc++.h>
using namespace std;
#define maxn 2005
#define gc getchar()
#define R(a) a = readint()
#define init(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = a; i <= b; i++)

const int inf = 0xcfcfcfcf;
int n;
int f[2][maxn];
struct node {
    int a, b;
    bool operator < (const node x) const {
        return a > x.a;
    }
}p[maxn];

inline int readint() {
    int x = 0, s = 1, c = gc;
    while (c <= 32)    c = gc;
    if (c == '-')    s = -1, c = gc;
    for (; isdigit(c); c = gc)
        x = x * 10 + c - 48;
    return x * s;
}

int main() {
    R(n);
    rep(i, 1, n) {
        R(p[i].a);
        R(p[i].b);
    }

    sort(p+1, p+1+n);
    init(f, 0xcf);
    f[0][0] = f[0][1] = 0;
    rep(i, 1, n) {
        rep(j, 0, n) {        
            if (j >= p[i].a) {
                f[i&1][j] = max(f[i-1&1][j], f[i-1&1][j+1-p[i].a] + p[i].b);
            } else {
                f[i&1][j] = max(f[i-1&1][j], f[i-1&1][1] + p[i].b);
            }
        }
    }
    
    printf("%d
", f[n&1][0]);
    return 0;    
}