2020-08-12 20:37 字节跳动_DATA-数据中台_后端研发工程师

关注

动态规划课程树型dp例题

string

http://www.nowcoder.com/questionTerminal/ea1026bf23af48a99445158235efd5e5

小G有一个大树

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 2000;
char buf[100000],*p1=buf,*p2=buf;
inline char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int w = 1, data = 0; char ch = 0;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = nc();
    if(ch == '-') w = -1, ch = nc();
    while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
    return w * data;
}
struct Edge {
    int to, next, w;
}edge[MAXN<<1];
int cnt, head[MAXN];
void add(int u, int v, int w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void add_edge(int u, int v, int w = 0) {
    add(u, v, w); add(v, u, w);
}
int n, siz[MAXN], root, temp = Inf;
void dfs(int x, int pre) {
    siz[x] = 1; int mx = 0;
    for(int i = head[x]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if(v == pre) continue;
        dfs(v, x); siz[x] += siz[v];
        mx = max(mx, siz[v]);
    }
    mx = max(mx, n - siz[x]);
    if(mx < temp) {
        temp = mx;
        root = x;
    }
}
int main() {
    n = read();
    memset(head, -1, sizeof head);
    for(int i = 1; i < n; i++) {
        int u = read(), v = read();
        add_edge(u, v);
    }
    dfs(1, -1);
    printf("%d %d", root, temp);
    return 0;
}

Rinne Loves Edges

设 $dp[u]$ 为以u为结点的子树，删最少多少边权可以使得所有叶子结点不到达根
对于一个节点的每一个分叉，一定会有一条边被转移，分出一个叉就代表一个至少一个子节点，那么对于每一颗子树，要么取其子树的结果，要么断掉和子树的边，取最小值转移即可
题目链接

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 1e5+10;
char buf[100000],*p1=buf,*p2=buf;
inline char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline ll read(){
    ll w = 1, data = 0; char ch = 0;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = nc();
    if(ch == '-') w = -1, ch = nc();
    while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
    return w * data;
}
struct Edge {
    int to, next;
    ll w;
}edge[MAXN<<1];
int cnt, head[MAXN], du[MAXN];
void add(int u, int v, ll w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
    du[u]++;
}
void add_edge(int u, int v, ll w = 0) {
    add(u, v, w); add(v, u, w);
}
int n, m, s;
ll dp[MAXN];
void dfs(int u, int pre) {
    if(du[u] == 1 && u != s) {
        dp[u] = Linf;
        return;
    }
    for(int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if(v == pre) continue;
        dfs(v, u);
        dp[u] += min(dp[v], edge[i].w);
    }
}
int main() {
    n = read(); m = read(); s = read();
    memset(head, -1, sizeof head);
    for(int i = 1; i <= m; i++) {
        int u = read(), v = read(), w = read();
        add_edge(u, v, w);
    }
    dfs(s, -1);
    printf("%lld", dp[s]);
    return 0;
}

Cell Phone Network

题目链接
每个点可以覆盖其相邻点，要求在树上选最少的点，使得整棵树被覆盖
考虑以 $x$ 为根的子树， $x$ 被覆盖有三种情况

$x$ 本身就被选择
$x$ 的儿子被选择
$x$ 的父亲被选择

发现 $x$ 的父亲对x也产生了影响，那么可以把父亲也设进x的状态，则dp的几个状态分别为

$dp[x][0]$ $x$ 自己被选择
$dp[x][4]$ $x$ 的儿子被选择
$dp[x][5]$ $x$ 的父亲被选择

那么考虑状态转移

$x$ 自己被选择时，其子节点选或者不选可以，且子节点不选的时候可以是其父节点 $x$ 被选，那么转移方程则为 $dp[x][0]=1+\sum{min(dp[v][0],dp[v][6],dp[v][7])}$
x的子树被选时，只需要其一个儿子被选就可以，那么对于其子树的两种选择1,2，先使 $dp[x][8]=\sum{min(dp[v][0],dp[v][9])}$ ,若 $x$ 的儿子统计的状态中有1状态，即 $x$ 的儿子本身被选择了，则 $x$ 就可以算被覆盖，若 $x$ 的所有儿子全部选择了2状态即 $x$ 的所有儿子本身没有被选择，而是 $x$ 的儿子 $v$ 再下一层的儿子被选择了，间接的把 $v$ 选择了，这种情况，需要在 $x$ 的众多儿子中挑一个被选择，那么挑的这个儿子就是从被其儿子覆盖，变成其本身被选择，改变量最小的，统计一下就可以了
$x$ 的父亲被选择的时候，那么其儿子可以被选择也可以不被选择，转移则为 $dp[x][10]=\sum{min(dp[v][0],dp[v][11])}$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 1e4+10;
char buf[100000],*p1=buf,*p2=buf;
inline char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int w = 1, data = 0; char ch = 0;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = nc();
    if(ch == '-') w = -1, ch = nc();
    while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
    return w * data;
}
struct Edge {
    int to, next, w;
}edge[MAXN<<1];
int cnt, head[MAXN];
void add(int u, int v, int w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void add_edge(int u, int v, int w = 0) {
    add(u, v, w); add(v, u, w);
}
int dp[MAXN][12], n;
//0 i 自己
//1 i 儿子
//2 i 父亲
void dfs(int u, int pre) {
    dp[u][0] = 1; int pos = Inf;
    dp[u][13] = 0; dp[u][14] = 0;
    for(int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if(v == pre) continue;
        dfs(v, u); 
        dp[u][0] += min(dp[v][0], min(dp[v][15], dp[v][16]));
        dp[u][17] += min(dp[v][0], dp[v][18]);
        dp[u][19] += min(dp[v][0], dp[v][20]);
        pos = min(pos, dp[v][0] - min(dp[v][0], dp[v][21]));
    }
    dp[u][22] += pos;
}
int main() {
    n = read();
    memset(head, -1, sizeof head);
    memset(dp, 0x3f, sizeof dp);
    for(int i = 1; i < n; i++) {
        int u = read(), v = read();
        add_edge(u, v);
    }
    dfs(1, 0);
    printf("%d", min(dp[1][0], dp[1][23]));
    return 0;
}

二叉苹果树

题目链接
因为题目要求的是保留 $q$ 条边最多的权值，那么就相当于选择 $q$ 条边使得这些边的路径可以到根节点1，把边权下放到点权，则相当于选 $q+1$ 个点，这些点连起来可以和根联通，这样的话若想选择点 $x$ ，则必须先选择 $x$ 的父节点 $fa[x]$ ,问题转换成了树形背包

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 500;
char buf[100000],*p1=buf,*p2=buf;
inline char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int w = 1, data = 0; char ch = 0;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = nc();
    if(ch == '-') w = -1, ch = nc();
    while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
    return w * data;
}
struct Edge {
    int to, next, w;
}edge[MAXN<<1];
int cnt, head[MAXN];
void add(int u, int v, int w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void add_edge(int u, int v, int w = 0) {
    add(u, v, w); add(v, u, w);
}
int n, q, val[MAXN], dp[MAXN][MAXN];

void dfs1(int u, int pre) {
    for(int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if(v == pre) continue;
        val[v] = edge[i].w;
        dfs1(v, u); 
        for(int j = q+1; j >= 0; j--)
            for(int k = j; k >= 0; k--)
                if(j - k  >= 0)
                    dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
    }
    for(int i = q+1; i >= 1; i--)
        dp[u][i] = dp[u][i-1] + val[u];
}
int main() {
    n = read(); q = read();
    memset(head, -1, sizeof head);
    for(int i = 1; i < n; i++) {
        int u = read(), v = read(), w = read();
        add_edge(u, v, w);
    }
    dfs1(1, -1);
    cout << dp[1][q+1];
    return 0;
}

没有上司的舞会

题目链接

设状态 $dp[u][0]$ 为不选择 $u$ 时权值最大最多是， $dp[u][1]$ 为选择 $u$ 时权值最大为多少

当选择 $u$ 的时候，其儿子全部不能选择，那么转移方程则为 $dp[u][1]=val[u]+\sum{dp[v][0]}$
当不选择 $u$ 的时候，其儿子可以选择也可以不选择，那么转移方程为 $dp[u][0]=\sum{max(dp[v][1],dp[v][0])}$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 2e4;
struct Edge {
    int to, next, w;
}edge[MAXN<<1];
int cnt, head[MAXN];
void add(int u, int v, int w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void add_edge(int u, int v, int w = 0) {
    add(u, v, w); add(v, u, w);
}
int n, dp[MAXN][2], r[MAXN], du[MAXN], ans;
void dfs(int u) {
    dp[u][1] = r[u];
    int mx1 = 0, mx0 = 0;
    for(int i = head[u]; i != - 1; i = edge[i].next) {
        int v = edge[i].to;
        dfs(v);
        mx1 += dp[v][0];
        mx0 += max(dp[v][0], dp[v][1]);
    }
    dp[u][1] = r[u] + mx1;
    dp[u][0] = mx0;
    ans = max(ans, max(dp[u][1], dp[u][0]));
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(head, -1, sizeof head);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> r[i];
    for(int i = 1; i < n; i++) {
        int l, k; cin >> l >> k;
        add(k, l); du[l]++;
    }
    int root;
    for(int i = 1; i <= n; i++) {
        if(du[i] == 0) root = i;
    }
    dfs(root);
    cout << ans;
    return 0;
}

Strategic game

题目链接

题目要求选择最少的点，覆盖所有的边，对于点 $x$ ,若选择 $x$ ,则其儿子结点可以选也可以不选，若不选 $x$ 结点，则其儿子结点必须全部都选,转移方程为

选 $x$ 结点： $dp[x][1]=\sum{min(dp[v][1],dp[v][0])}$
不选 $x$ 结点： $dp[x][0] = \sum{dp[v][1]}$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 2000;
int n;
struct Edge {
    int to, next, w;
}edge[MAXN<<1];
int cnt, head[MAXN];
void add(int u, int v, int w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void add_edge(int u, int v, int w = 0) {
    add(u, v, w); add(v, u, w);
}
void init() {
    cnt = 0;
    memset(head, -1, sizeof head);
}
int vis[MAXN], dp[MAXN][2];
void dfs(int u, int pre) {
    vis[u] = 1; dp[u][1] = 1; dp[u][0] = 0;
    for(int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if(v == pre) continue;
        dfs(v, u);
        dp[u][0] += dp[v][1];
        dp[u][1] += min(dp[v][1], dp[v][0]);
    }
}
void doit() {
    init();
    for(int i = 1; i <= n; i++) {
        char s[100]; scanf("%s", s);
        int x = 0, m = 0, top = 0;
        while(s[top] != ':') x = x*10 + s[top++]-'0';
        top += 2; while(s[top] != ')') m = m*10 + s[top++]-'0';
        for(int j = 1; j <= m; j++) {
            int v; scanf("%d", &v);
            add_edge(x, v);
        }
    }
    memset(dp, 0x3f, sizeof dp);
    memset(vis, 0, sizeof vis);
    int ans = 0;
    for(int i = 0; i < n; i++) {
        if(!vis[i]) dfs(i, -1), ans += min(dp[i][0], dp[i][1]);
    }
    cout << ans << endl;
}
int main() {
    while(scanf("%d", &n) != EOF) doit();
    return 0;
}

树上子链

题目链接

对于每个结点 $x$ 来说，其最最长链肯定为它的最长子链和次长子链之和，统计一下就可以了，本题需要注意的是，因为点权可以为负数，那么有可能出现只选一个点的情况，答案记录的时候初始值要为 $-Inf$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 1e5+10;
char buf[100000],*p1=buf,*p2=buf;
inline char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int w = 1, data = 0; char ch = 0;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = nc();
    if(ch == '-') w = -1, ch = nc();
    while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
    return w * data;
}
struct Edge {
    int to, next, w;
}edge[MAXN<<1];
int cnt, head[MAXN];
void add(int u, int v, int w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void add_edge(int u, int v, int w = 0) {
    add(u, v, w); add(v, u, w);
}
int n, val[MAXN];
ll dp[MAXN], ans = -Linf;
void dfs(int u, int pre) {
    dp[u] = 0; ans = max(ans, 1ll* val[u]);
    for(int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if(v == pre) continue;
        dfs(v, u);
        ans = max(ans, dp[u] + dp[v] + 1ll*val[u]);
        dp[u] = max(dp[v], dp[u]);
    }
    dp[u] += val[u];
}
int main() {
    n = read();
    memset(head, -1, sizeof head);
    for(int i = 1; i <= n; i++) val[i] = read();
    for(int i = 1; i < n; i++) {
        int u = read(), v = read();
        add_edge(u, v);
    }
    dfs(1, -1);
    cout << ans;
    return 0;
}

吉吉王国

题目链接

没开 $long long$ 调了一个小时......

实际上就是 Rinne Loves Edges 这道题的一个变形，要求删去的最长长度最小，那么二分这个长度 $x$ ,设 $dp[x]$ 为以 $x$ 点为根的子树的最小花费，所以边长大于 $x$ 的边全部不删，直接转移子树的答案，若边长小于等于 $x$ 则这条边可以删也可以不删，比较下删这条边还是这个子树的代价，取更小的。

二分答案求解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 1e6+10;
char buf[100000],*p1=buf,*p2=buf;
inline char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline ll read(){
    ll w = 1, data = 0; char ch = 0;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = nc();
    if(ch == '-') w = -1, ch = nc();
    while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
    return w * data;
}
ll n, m;
struct Edge {
    ll to, next, w;
}edge[MAXN<<1];
ll cnt, head[MAXN], du[MAXN];
void add(ll u, ll v, ll w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
    du[u]++;
}
void add_edge(ll u, ll v, ll w = 0) {
    add(u, v, w); add(v, u, w);
}
ll dp[MAXN];
void dfs(ll u, ll pre, ll lim) {
    if(du[u] == 1 && u != 1) {
        dp[u] = Inf;
        return;
    }
    dp[u] = 0;
    for(ll i = head[u]; i != -1; i = edge[i].next) {
        ll v = edge[i].to;
        if(v == pre) continue;
        dfs(v, u, lim);
        if(edge[i].w > lim) dp[u] += dp[v];
        else dp[u] += min(dp[v], edge[i].w);
    }
}
bool check(ll lim) {
    dfs(1, -1, lim);
    return dp[1] <= m;
}
int main() {
    memset(head, -1, sizeof head);
    n = read(); m = read();
    for(ll i = 1; i < n; i++) {
        ll u = read(), v = read(), w = read();
        add_edge(u, v, w);
    }
    ll l = 0, r = 2000, ans = -1;
    while(l <= r) {
        ll mid = (l + r) >> 1;
        if(check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    cout << ans;
    return 0;
}