动态规划专题(三)

这篇文章主要介绍背包问题和区间dp问题

多重背包

多重背包常见的优化有二进制拆分
还有单调队列优化

POJ1742
POJ1742-02

const int maxm = 100000 + 5, maxn = 1000 + 5;

int A[maxn], C[maxn];

int N2 = 1;
int N, M;
bitset<maxm> f;

void initdp() {
    N2 = 1;
    f &= 1;
    f[0] = 1;
}


int dp() {
    _rep(i, 1, N) {
        for(int p = 1; p <= C[i]; p <<= 1) {
            //
            f |= (f << (p * A[i]));
            C[i] -= p;
        }
        if(C[i]) f |= (f << (C[i] * A[i]));
    }

    int ans = 0;
    _rep(i, 1, M) if(f[i]) ans += f[i];
    return ans;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d", &N, &M) == 2 && N) {
        _rep(i, 1, N) scanf("%d", &A[i]);
        _rep(i, 1, N) scanf("%d", &C[i]);

        // then dp
        initdp();

        cout << dp() << endl;
    }
}

分组背包

groupPack

区间dp

分析方法和模版

POJ1179-01
POJ1179-02

CH5301
本例作为模版

const int maxn = 300 + 5;
const int inf = 0x3f;
int A[maxn];
int N;
int f[maxn][maxn];
int sum[maxn];

void initdp() {
    Set(sum, 0);
    Set(f, inf);
    _rep(i, 1, N) {
        sum[i] = sum[i - 1] + A[i];
        assert(sum[i] != 0);
        f[i][i] = 0;
    }
}

void dp() {
    _rep(len, 2, N) _rep(l, 1, N - len + 1) {
        int r = l + len - 1;
        for(int k = l; k < r; k++) f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);

        f[l][r] += (sum[r] - sum[l - 1]);
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    _rep(i, 1, N) {
        scanf("%d", &A[i]);
        //debug(A[i]);
    }

    initdp();
    dp();

    printf("%d\n", f[1][N]);
}

POJ1179

const int maxn = 100 + 5;
const int inf = 0x3f3f3f3f;

struct Node {
    int x;
    char op;
};

Node nodes[maxn];
int Fmax[maxn][maxn], Fmin[maxn][maxn];
int N;

void initdp() {
    Set(Fmax, -inf);
    Set(Fmin, inf);

    _rep(i, 1, (N << 1)) {
        Fmax[i][i] = Fmin[i][i] = nodes[i].x;
        assert(Fmax[i][i] != -inf && Fmin[i][i] != inf);
    }
}

void dp() {
    _rep(len, 2, N) {
        for(int l = 1; l + len - 1 <= (N << 1); l++) {
            int r = l + len - 1;
            _rep(k, l + 1, r) {
                if(nodes[k].op == 't') {
                    // update Fmax and Fmin
                    Fmax[l][r] = max(Fmax[l][r], Fmax[l][k - 1] + Fmax[k][r]);
                    Fmin[l][r] = min(Fmin[l][r], Fmin[l][k - 1] + Fmin[k][r]);
                }
                else {
                    // update Fmax and Fmin, much more complicate
                    Fmax[l][r] = max(Fmax[l][r], max(Fmax[l][k - 1] * Fmax[k][r], Fmin[l][k - 1] * Fmin[k][r]));
                    Fmin[l][r] = min(Fmin[l][r], min(Fmin[l][k - 1] * Fmin[k][r], min(Fmax[l][k - 1] * Fmax[k][r], min(Fmin[l][k - 1] * Fmax[k][r], Fmax[l][k - 1] * Fmin[k][r]))));
                }
            }
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    _rep(i, 1, N) {
        int x;
        char op;
        cin >> op >> x;
        nodes[i].op = op;
        nodes[i].x = x;
        //debug(nodes[i].x);
    }
    _rep(i, N + 1, (N << 1)) {
        nodes[i] = nodes[i - N];
        assert(nodes[i].x == nodes[i - N].x && nodes[i].op == nodes[i - N].op);
    }

    initdp();
    dp();

    int ans = -inf;
    _rep(i, 1, N) ans = max(ans, Fmax[i][i + N - 1]);
    cout << ans << endl;

    _rep(i, 1, N) if(Fmax[i][i + N - 1] == ans) cout << i << " ";
}

区间dp的递归算法和记忆化搜索

CH5302
CH5302

const int maxn = 300 + 5;
const int MOD = 1000000000;
char str[maxn];
int N;
int f[maxn][maxn];

void initdp() {
    Set(f, -1);
}

int dp(int l, int r) {
    if(l > r) return 0;
    if(l == r) return 1;
    int& ans = f[l][r];
    if(ans != -1) return ans;

    ans = 0;
    if(str[l] == str[r]) {
        for(int k = l + 2; k <= r; k++) {
            ans = (ans + (llong)dp(l + 1, k - 1) * (llong)dp(k, r)) % MOD;
        }
    }

    return ans;
}


int main() {
    freopen("input.txt", "r", stdin);
    scanf("%s", str + 1);
    N = strlen(str + 1);

    initdp();
    cout << dp(1, N) << endl;
}

树形dp

模版题

CH5401

const int maxn = 6000 + 5;
int H[maxn];
bool hasFa[maxn];
int f[maxn][2];
vector<int> son[maxn];
int N;

void initdp() {
    Set(f, 0);
}

void dp(int x) {
    f[x][1] = H[x];
    f[x][0] = 0;
    _for(i, 0, son[x].size()) {
        int y = son[x][i];
        dp(y);

        f[x][0] += max(f[y][0], f[y][1]);
        f[x][1] += f[y][0];
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> N;

    _rep(i, 1, N) scanf("%d", &H[i]);
    _for(i, 0, N) {
        int x, y;
        scanf("%d%d", &x, &y);
        hasFa[x] = 1;
        son[y].push_back(x);
    }

    int root = 0;
    _rep(i, 1, N) if(!hasFa[i]) {
        root = i;
        break;
    }
    assert(root != 0);

    initdp();
    // then dp
    dp(root);
    cout << max(f[root][0], f[root][1]) << endl;
}

树形dp和背包综合

CH5402

CH5402

const int maxn = 300 + 5;
int score[maxn];
vector<int> son[maxn];
int N, M;

int f[maxn][maxn];
const int inf = 0xcf;

void initdp() {
    Set(f, inf);
}

void dp(int x) {
    f[x][0] = 0;
    _for(i, 0, son[x].size()) {
        int y = son[x][i];
        dp(y);

        _forDown(t, M, 0) {
            _forDown(j, t, 0) {
                if(t - j < 0) continue;
                f[x][t] = max(f[x][t], f[x][t - j] + f[y][j]);
            }
        }
    }

    if(x) for(int t = M; t > 0; t--) f[x][t] = f[x][t - 1] + score[x];
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> N >> M;

    _rep(i, 1, N) {
        int x;
        cin >> x >> score[i];
        son[x].push_back(i);
    }

    initdp();
    dp(0);
    cout << f[0][M] << endl;
}

树形dp, 二次扫描与换根

POJ3585
POJ3585

const int maxn = 200000 + 10;
const int inf = 0x3f;
int N;

class Graph {
public:
    int tot;
    int head[maxn], ver[maxn * 2], nxt[maxn * 2];
    int w[maxn * 2];

    void clear() {
        tot = 1;
        Set(head, 0);
        Set(ver, 0);
        Set(nxt, 0);
        Set(w, 0);
    }

    void add(int x, int y, int z) {
        ver[++tot] = y;

        w[tot] = z;

        nxt[tot] = head[x];
        head[x] = tot;
    }
};

Graph G;
int deg[maxn], vis[maxn];
int ds[maxn], f[maxn];

void init() {
    G.clear();
    Set(deg, 0);
    Set(vis, 0);
    Set(ds, 0);
    Set(f, 0);
}

void dp(int x) {
    assert(vis[x] == 0);
    ds[x] = 0;
    vis[x] = 1;

    for(int i = G.head[x]; i; i = G.nxt[i]) {
        int y = G.ver[i];
        if(vis[y]) continue;
        dp(y);

        if(deg[y] == 1) ds[x] += G.w[i];
        else ds[x] += min(G.w[i], ds[y]);
    }
}

void initdfs(int root) {
    Set(vis, 0);
    f[root] = ds[root];
}

void dfs(int x) {
    vis[x] = 1;
    for(int i = G.head[x]; i; i = G.nxt[i]) {
        int y = G.ver[i];
        if(vis[y]) continue;

        int flow = min(ds[y], G.w[i]);
        if(deg[x] == 1) f[y] = ds[y] + G.w[i];
        else {
            f[y] = ds[y] + min(G.w[i], f[x] - flow);
        }

        dfs(y);
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);

    while (T--) {
        init();
        scanf("%d", &N);

        _for(i, 1, N) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            G.add(x, y, z);
            G.add(y, x, z);

            deg[x]++;
            deg[y]++;
        }

        // then dp
        int root = 1;
        dp(root);

        initdfs(root);
        dfs(root);

        int ans = 0;
        _rep(i, 1, N) ans = max(ans, f[i]);

        cout << ans << endl;
    }
}