您的位置: 首页  >  IT文章  >  树型DP简单入门

树型DP简单入门

分类: IT文章 • 2024-02-03 14:11:13

一道入门必做的题目

Anniversary party 题目链接

思路

里面的关系是一个树状的无环图，每个节点我们显然有两种取法，参加派对，不参加派对，所以状态转移方程就出来了

  • 参加派对 (dp[i][1] = dp[i][1] + dp[i_{son}][0])，上司参加了舞会，其直系下属不能参加舞会
  • 不参加派对 (dp[i][0] = dp[i][0] + max(dp[i_{son}][1], dp[i_{son}][0]))，上司没有参加舞会，其直系下属可以参加，也可以不参加。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;

int head[N], to[N], nex[N], in[N], cnt = 1;

int dp[N][2], n;

void add(int x, int y) {
    to[cnt] = y;
    nex[cnt] = head[x];
    head[x] = cnt++;
    in[y]++;
}

void dfs(int rt, int fa) {
    for(int i = head[rt]; i; i = nex[i]) {
        if(to[i] != fa) {
            dfs(to[i], rt);
            dp[rt][1] += dp[to[i]][0];
            dp[rt][0] += max(dp[to[i]][0], dp[to[i]][1]);
        }
    }
}
int main() {
    // freopen("in.txt", "r", stdin);
    while(scanf("%d", &n) != EOF) {
        cnt = 1;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &dp[i][1]);
            head[i] = 0;
            dp[i][0] = 0;
        }
        int x, y;
        while(scanf("%d %d", &x, &y) && (x + y))
            add(y, x);
        for(int i = 1; i <= n; i++)
            if(!in[i]) {
                dfs(i, 0);
                printf("%d
", max(dp[i][0], dp[i][1]));
            }
    }
    return 0;
}

一道比入门题还简单的题

P2996 [USACO10NOV]Visiting Cows G

代码

入门题都懂了，这题想必大佬们肯定能写。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int head[N], to[N], nex[N], cnt = 1;
int dp[N][2], n;

void add(int x, int y) {
    to[cnt] = y;
    nex[cnt] = head[x];
    head[x] = cnt++;
}

void dfs(int rt, int fa) {
    for(int i = head[rt]; i; i = nex[i]) {
        if(to[i] != fa) {
            dfs(to[i], rt);
            dp[rt][1] += dp[to[i]][0];
            dp[rt][0] += max(dp[to[i]][0], dp[to[i]][1]);
        }
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    int x, y;
    scanf("%d", &n);
    for(int i = 1; i < n; i++) {
        scanf("%d %d", &x, &y);
        add(x, y);
        add(y, x);
        dp[i][1] = 1;
    }
    dp[n][1] = 1;
    dfs(1, 0);
    printf("%d
", max(dp[1][0], dp[1][1]));
    return 0;
}

一道思路对了，但是细节把我击垮了的题目

Rebuilding Roads 题目链接

思路

思路不难，dp[i][j]数组，记录的时第i个节点加上其子树上与其相连的节点的数量时j时，需要切断的路径显然有dp[i][1] = 与其直接相连的子树加上一个父节点的路径。

然后状态转移方程就有了 (dp[i][j] = min(dp[i][j], dp[i][k] + dp[i_{son}][j - k] - 2))，这个减二的操作是因为，这两个之间相连的边都在互相的dp数组中记录了，所以需要减去2。

接下来就要说一个细节了，我们在最后的答案中dp[root][]中所有的都要减去1，因为在之前我们把其父节点的边加进去了，但是他是没有父节点的。这个点，坑人啊，还是太菜了。

代码

// #include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 2e2 + 10;

int head[N], to[N], nex[N], in[N], cnt;

int dp[N][N], sz[N], n, m;

void add(int x, int y) {
    to[cnt] = y;
    nex[cnt] = head[x];
    head[x] = cnt++;
    in[y]++;
}
void dfs1(int rt, int fa) {//寻找直接相连的结点数，初始化dp数组。
    sz[rt] = 1;
    for(int i = head[rt]; i; i = nex[i]) {
        if(to[i] != fa) {
            dfs1(to[i], rt);
            sz[rt] ++;
        }
    }
}

void solve(int rt, int fa) {
    for(int i = head[rt]; i ; i = nex[i]) {
        if(to[i] != fa) {
            solve(to[i], rt);
            for (int j = m; j > 1; j--)
            for (int k = 1; k < j; k++)
                dp[rt][j] = min(dp[rt][j], dp[rt][j - k] + dp[to[i]][k] - 2);
        }
    }
}
int main() {
    // freopen("in.txt", "r", stdin);
    int x, y;
    while(scanf("%d %d", &n, &m) != EOF) {
        memset(head, 0, sizeof head);
        memset(dp, 0x3f, sizeof dp);
        cnt = 1;
        for(int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            add(x, y);
        }
        for(int i = 1; i <= n; i++)
            if(in[i] == 0) {
                // cout << i << endl;
                dfs1(i, 0);
            }
        for(int i = 1; i <= n; i++)//好像可以直接在dfs1中完成，，，，
            dp[i][1] = sz[i];
            // cout << sz[i] << endl;
        for(int i = 1; i <= n; i++)
            if(in[i] == 0) {
                solve(i, 0);
                dp[i][m]--;
            }
        // for(int i = 1; i <= n; i++)//调试bug_ing
        //     for(int j = 1; j <= m; j++) {
        //         printf("%d%c", dp[i][j], j == m ? '
' : ' ');
        //     }
        int ans = 0x3f3f3f3f;
        for(int i = 1; i <= n; i++)
            dp[i][m] < ans ? ans = dp[i][m] : ans = ans;//终于出答案了，写了一长串我现在看不懂的表达式，，，，
        printf("%d
", ans);
    }
    return 0;
}

一道稍微复杂一点的题目

其实也挺好理解的。

最优连通子集 题目链接

思路

这是一道要自己建图的题，显然我们不难想到，在dis = 1的两个点之间建立联通的边，接下来的事情就是树上DP了。

考虑状态转移方程，对于每一个点我们可以将其放入联通集或者不放入联通集，同时我们还要保证，每一个点对都是互相连通的。

我们用dp[i][0]表示这个点不在联通集上，用dp[i][1]表示这个点在联通集上。

考虑dp[i][0]如何变化，不难发现他的值一定是其子树上的最大值，所以 (dp[i][0] = max(dp[i][0], dp[i_{son}][1], dp[i_{son}][0]))

接着我们考虑dp[i][1]，我们要保证它的连通性，得到 (dp[i][1] = max(dp[i][1], dp[i_{son}][1] + dp[i][1]))

然后按照这个思路跑一遍DFS就行了。

代码

// #include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N1 = 1e3 + 10, N2 = 1e6 + 10;

int head[N1], to[N2], nex[N2], cnt;

int dp[N1][2], n;

struct point {
    int x, y;
}a[N1];

void add(int x, int y) {
    to[cnt] = y;
    nex[cnt] = head[x];
    head[x] = cnt++;
}

void dfs(int rt, int fa) {
    for(int i = head[rt]; i; i = nex[i]) {
        if(to[i] != fa) {
            // cout << 1 << endl;
            dfs(to[i], rt);
            dp[rt][1] = max(dp[rt][1], dp[rt][1] + dp[to[i]][1]);
            dp[rt][0] = max(dp[rt][0], max(dp[to[i]][0], dp[to[i]][1]));
        }
    }

}

int main() {
    // freopen("in.txt", "r", stdin);
    int x, y, w;
    while(scanf("%d", &n) != EOF) {
        for(int i = 1; i <= n; i++)
            dp[i][0] = dp[i][1] = head[i] = 0;
        cnt = 1;
        for(int i = 1; i <= n; i++) {
            scanf("%d %d %d", &a[i].x, &a[i].y, &w);
            dp[i][1] = w;
        }
        for(int i = 1; i <= n; i++)
            for(int j = i + 1; j <= n; j++)
                if((abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y)) == 1) {
                    add(i, j), add(j, i);
                    // cout << 1 << endl;
                }
        dfs(1, 0);
        // for(int i = 1; i <= n; i++)
        //     printf("%d %d
", dp[i][0], dp[i][1]);
        printf("%d
", max(dp[1][0], dp[1][1]));
    }
    return 0;
}

本来应该还有第四道题，没想到考察了树上背包，但是这个东西我还没学过啊，就先咕咕咕咕咕下了。

相关推荐