CONTENT: DP - II



BB

最近Practice系列的，所以等有一定量再更新，当然一个月多没更新是因为我在划水 QAQ

Let the light guide us - HDU 3698

Link
https://cn.vjudge.net/problem/HDU-3698
Description
给定t[i][j]与f[i][j]，在满足每一行只选一个t[i][j]，且满足|j - k| <= f[i][j] + f[i - 1][k]的情况下，t[i][j]之和最小值。本题范围为2<=N<=100 , 1<=M<=5000, 0<=Tij, Fij<=100000
Sample Input

3 5
9 5 3 8 7
8 2 6 8 9
1 9 7 8 6
0 1 0 1 2
1 0 2 1 1
0 2 1 0 2
0 0

Sample Output

10

Solution —— DP + 线段树优化
首先，本题的DP方程是明显的，即定义dp(i, j)为前i行在第i行选第j个的最小值，那么
dp(i, j) = t(i, j) + min{ dp(i - 1, k) | |j - k| <= f(i, j) + f(i - 1, k) } (1 <= k <= m)
但是复杂度高达O(nm^2)，是不可接受的
上述dp的瓶颈在于需要枚举k确定dp(i - 1, k)的最小值，而需要枚举的原因是约束不等式
现在拆这个不等式，可得-f(i, j) - f(i - 1, k) <= j - k <= f(i, j) + f(i - 1, k)，可得j - f(i - j) <= f(i - 1, k) + k且j + f(i, j) >= k - f(i - 1, k)，即区间[j - f(i, j), j + f(i, j)]与区间[k - f(i - 1, k), k + f(i - 1, k)]有交集
因此当dp到第i层时，用线段树把上一层的[k - f(i - 1, k), k + f(i - 1, k)]区间置为dp所能达到的最小值，那么
dp(i, j) = t(i + j) + query([j - f(i, j), j + f(i, j)])
总复杂度O(nm’log(m’))

#include <bits/stdc++.h>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int M = 5015;
const int N = 1e5 + M;

ll seg[N << 2], lzy[N << 2], dp[M];
int tim[105][M], f[105][M];
int maxd[105];

inline char get(void) {
    static char buf[1000000];
    static char* p1 = buf;
    static char* p2 = buf;
    if (p1 == p2) {
        p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
        if (p1 == p2) return EOF;
    }
    return (*p1++);
}

inline int read() {
    int x = 0; static char c; bool minus = false;
    for (; !(c >= '0' && c <= '9'); c = get()) if (c == '-') minus = true;
    for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); if (minus) x = -x;
    return x;
}

inline void pushUp(int rt) {
    seg[rt] = min(seg[rt << 1], seg[rt << 1 | 1]);
}

inline void pushDown(int rt) {
    if(lzy[rt] != inf) {
        lzy[rt << 1] = min(lzy[rt << 1], lzy[rt]);
        lzy[rt << 1 | 1] = min(lzy[rt << 1 | 1], lzy[rt]);
        seg[rt << 1] = min(seg[rt << 1], lzy[rt]);
        seg[rt << 1 | 1] = min(seg[rt << 1 | 1], lzy[rt]);
        lzy[rt] = inf;
    }
}

inline void update(int ql, int qr, ll val, int l, int r, int rt) {
	if(ql <= l && r <= qr) {
	   seg[rt] = min(seg[rt], val);
     lzy[rt] = min(lzy[rt], val);
     return;
	}
	pushDown(rt);
	int m = (l + r) >> 1;
	if(ql <= m) {
     update(ql, qr, val, lson);
	}
	if(m < qr) {
     update(ql, qr, val, rson);
	}
	pushUp(rt);
}

inline ll query(int ql, int qr, int l, int r, int rt) {
    if(ql <= l && r <= qr) {
        return seg[rt];
    }
    pushDown(rt);
    int m = (l + r) >> 1;
    ll ans = inf;
    if(ql <= m) {
        ans = min(ans, query(ql, qr, lson));
    }
    if(m < qr) {
        ans = min(ans, query(ql, qr, rson));
    }
    return ans;
}

int main() {
    int n, m;
    while(true) {
        memset(maxd, 0, sizeof(maxd));

        n = read();
        m = read();
        if(n == 0 && m == 0) {
            break;
        }

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                tim[i][j] = read();
            }
        }

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                f[i][j] = read();
                maxd[i] = max(maxd[i], f[i][j] + j + 5);
            }
        }

        for(int j = 1; j <= m; j++) {
            dp[j] = tim[1][j];
        }

        for(int i = 2; i <= n; i++) {
            memset(seg, 0x3f, 4 * maxd[i] * sizeof(ll));
            memset(lzy, 0x3f, 4 * maxd[i] * sizeof(ll));
            for(int k = 1; k <= m; k++) {
                update(max(k - f[i - 1][k], 0) + 1, f[i - 1][k] + k + 1, dp[k], 1, maxd[i], 1);
            }
            for(int j = 1; j <= m; j++) {
                dp[j] = tim[i][j] + query(max(j - f[i][j], 0) + 1, j + f[i][j] + 1, 1, maxd[i], 1);
            }
        }

        ll ans = inf;
        for(int i = 1; i <= m; i++) {
            ans = min(ans, dp[i]);
        }
        printf("%lld\n", ans);
    }
}


GeoDefense - HDU 4044

Link
https://cn.vjudge.net/problem/HDU-4044
Description
给定一棵树，以1为根，在每个点都有ki种炮塔可供选择，每种炮塔为(price, power)，每个点最多只能建一个炮塔，先给定初始price，问在建造炮塔总price不超过所给定初始price的情况下，根到叶子节点的每条路径上的power之和中的最小值，要求这个值最大
Sample Input

2
2
1 2
30
3 10 20 20 40 30 50
3 10 30 20 40 30 45
4
2 1
3 1
1 4
60
3 10 20 20 40 30 50
3 10 30 20 40 30 45
3 10 30 20 40 30 35
3 10 30 20 40 30 35

Sample Output

70
80

Solution —— 树形DP + 分组背包
定义dp(u, mon)为点u及其子树在总price为mon的情况下，u到叶子节点的每条路径的最大最小值，那么
dp'(u, mon) = (each v = son(u), knapsackMax{ dp(v, monv), 1 <= monv <= mon })
dp(u, mon) = (each tower, knapsackMax { power + dp'(u, mon - price) })
对于第一个方程，对u的每一个分支做分组背包，选其中丢进容量为mon的背包后能使得最小值最大的一个，那么最后dp(u, mon)就是本身不建炮塔时的最优方案
对于第二个方程，考虑建炮塔，把炮塔丢进去做分组背包，选值最大的一个
虽然列了两个方程，但实际上开一个dp数组就行

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e3 + 15;
const int M = 205;
const int inf = 0x3f3f3f3f;

struct edge {
    int v, nxt;
};
int head[N], tot;
edge e[N << 1];
vector<int> kmon[N], kden[N];
int dp[N][M];

inline void init() {
    memset(head, -1, sizeof(head));
    memset(dp, 0, sizeof(dp));
    tot = 0;
}

inline void addEdge(int u, int v) {
    e[tot] = edge{v, head[u]};
    head[u] = tot++;
}

void dfs(int u, int pre) {
    bool isFirst = true;
    for(int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if(v == pre) {
            continue;
        }
        dfs(v, u);

        if(isFirst) {
            for(int mon = 0; mon < M; mon++) {
                dp[u][mon] = dp[v][mon];
            }
            isFirst = false;
            continue;
        }

        for(int mon = M - 1; mon >= 0; mon--) {
            int maxx = 0;
            for(int monv = 0; monv <= mon; monv++) {
                maxx = max(maxx, min(dp[u][mon - monv], dp[v][monv]));
            }
            dp[u][mon] = maxx;
        }
    }

    for(int mon = M - 1; mon >= 0; mon--) {
        int maxx = dp[u][mon];
        for(int i = 0; i < (int)kmon[u].size(); i++) {
            if(kmon[u][i] <= mon) {
                maxx = max(maxx, dp[u][mon - kmon[u][i]] + kden[u][i]);
            }
        }
        dp[u][mon] = maxx;
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        init();

        int n, mon;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            kmon[i].clear();
            kden[i].clear();
        }
        for(int i = 1; i <= n - 1; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            addEdge(u, v);
            addEdge(v, u);
        }
        scanf("%d", &mon);
        for(int i = 1; i <= n; i++) {
            int k;
            scanf("%d", &k);
            while(k--) {
                int mon, den;
                scanf("%d%d", &mon, &den);
                kmon[i].emplace_back(mon);
                kden[i].emplace_back(den);;
            }
        }
        dfs(1, -1);

        printf("%d\n", dp[1][mon]);
    }
}


Bookshelves - CodeForces 981D

Link
https://cn.vjudge.net/problem/CodeForces-981D
Description
给定一个长度为n的序列，要求分成k段，求每段之和相与的最大值
Sample Input

10 4
9 14 28 1 7 13 15 29 2 31

7 3
3 14 15 92 65 35 89

Sample Output

24
64


Solution —— 贪心 + DP + 枚举 + 动态维护
（本题为jjdl钦点题目！） 首先需要肯定一点，两段之和分别取最大值再相与不能取得所求值，因为可能有一段的值为1000，另一段为0111，相与后答案为0，而左边可能能取到0111，相与后为0111
通过上述例子可以发现，实际上二进制与的决定因素在高位，因此考虑从高位向低位贪心DP，但问题是如何保留上一次的结果？
（翻了一下Solution后，划掉）可以采用枚举假设的方法维护最大值，现在从高位出发，假设高位为1，那么此时的值为100…000，记为ans，然后DP，设dp(i, k)为前i个数分为k段高位能否为ans，那么
dp(i, k) = or{ dp(j, k - 1) and (sum(j + 1, i) & ans == ans) }
如果最终dp(n, k)为true，那么保留这一位为1的结果，否则置为0，那么下一次dp便可以利用之前dp的结果

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 75;

ll sum[N];
bool ok[N][N];

bool isCan(int n, int kk, const ll& ans) {
    memset(ok, false, sizeof(ok));

    for(int i = 1; i <= n; i++) {
        ok[i][1] = ((sum[i] & ans) == ans);
    }
    for(int k = 2; k <= kk; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i - 1; j++) {
                ok[i][k] |= (ok[j][k - 1] & (((sum[i] - sum[j]) & ans) == ans));
            }
        }
    }
    return ok[n][kk];
}

int main() {
    int n, k;
    while(~scanf("%d%d", &n, &k)) {
        for(int i = 1; i <= n; i++) {
            scanf("%lld", &sum[i]);
            sum[i] += sum[i - 1];
        }

        ll ans = 0;
        for(int p = 60; p >= 0; p--) {
            ans = ans | (1LL << p);
            if(!isCan(n, k, ans)) {
                ans ^= (1LL << p);
            }
        }
        printf("%lld\n", ans);
    }
}