动态规划课程树型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

为以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

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

  1. 本身就被选择
  2. 的儿子被选择
  3. 的父亲被选择

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

  1. 自己被选择
  2. 的儿子被选择
  3. 的父亲被选择

那么考虑状态转移

  1. 自己被选择时,其子节点选或者不选可以,且子节点不选的时候可以是其父节点 被选,那么转移方程则为
  2. x的子树被选时,只需要其一个儿子被选就可以,那么对于其子树的两种选择1,2,先使 ,若 的儿子统计的状态中有1状态,即 的儿子本身被选择了,则 就可以算被覆盖,若 的所有儿子全部选择了2状态即 的所有儿子本身没有被选择,而是 的儿子 再下一层的儿子被选择了,间接的把 选择了,这种情况,需要在 的众多儿子中挑一个被选择,那么挑的这个儿子就是从被其儿子覆盖,变成其本身被选择,改变量最小的,统计一下就可以了
  3. 的父亲被选择的时候,那么其儿子可以被选择也可以不被选择,转移则为
#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;
}

二叉苹果树

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

#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;
}

没有上司的舞会

题目链接

设状态 为不选择 时权值最大最多是, 为选择 时权值最大为多少

  1. 当选择 的时候,其儿子全部不能选择,那么转移方程则为
  2. 当不选择 的时候,其儿子可以选择也可以不选择,那么转移方程为
#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

题目链接

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

  1. 结点:
  2. 不选 结点:
#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;
}

树上子链

题目链接

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

#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;
}

吉吉王国

题目链接

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

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

二分答案求解

#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;
}
全部评论

相关推荐

lingo12:1.最好加个业务项目,大部分面试官工作以后会更偏重业务 2.实习部分描述一般般,可能hr看到会觉得你产出不够不给你过简历 3.蓝桥杯这些大部分人都有的,不如不写,反而减分项。
点赞 评论 收藏
分享
hanliu:1. 排版与格式问题字体与对齐问题:标题和内容的字体大小差异不够明显,无法迅速吸引目光。某些文字看起来有些拥挤(比如校园经历中的“班委成员”部分)。2. 内容逻辑性模块顺序问题:实习经历放在较靠后的位置,实际上这部分内容对应聘来说更重要,建议提前突出。细节表述不够突出:比如教育背景部分的专业课程仅仅列出名字,没有说明自己在这些课程中表现如何或者掌握了什么技能,缺乏量化描述。多余内容:例如“班委成员”和“宣传委员”这类校园经历,叙述过于普通,缺乏和岗位相关的实质性贡献。,建议简写。3. 措辞专业性表达不够精准:例如“协助班长与团支书更好地为同学服务”显得较为笼统,没有实际成果的体现。用词重复:如“学习了焊接”“学习了光检”等重复词语较多,缺乏丰富的动词来展示个人能力(如“负责”“优化”“改进”等)。技能展示不足:虽然列出了UG和CAD证书,但没有明确提到这些技能如何在实际工作中发挥作用。4. 技能匹配度技能深度不足:虽然列出了掌握的软件和技术,但没有描述技能水平(如“熟练掌握”“精通”),也没有具体案例支持这些技能。缺乏岗位导向性:比如针对机械设计与制造方向,实习经历提到了“E6尾灯项目”,但没有详细说明自己在其中的技术贡献,可能会显得经验描述泛泛而谈。5. 自我评价问题表达空泛:如“具有良好的沟通协调能力”“责任心强”之类的描述太常见,没有让人眼前一亮的特点。缺乏成果支持:自我评价中的能力没有用具体项目、经历或成就来验证,可信度较弱。 兄弟加油
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务