P7201 [COCI 2019/2020 #1] Džumbus 题解

· · 题解

可能更好的食用体验 | 题目传送门 | 我的其他题解

{\color{#00CD00}\text{题意}}

给定一个 n 个结点，m 条无向边的森林。初始时每个点都是白色的，可以花费 a_u 的代价将结点 u 染成黑色。对于一个结点，若其自身为黑色，且至少有一个子结点也为黑色，则称这个结点是「好的」。Q 次询问，每次询问给出一个整数 S，求花费不超过 S 的代价最多能获得多少个「好的」结点。

建议评分为蓝/紫。 ------------ ### ${\color{#00CD00}\text{思路}}

增加一个虚拟结点 0 作为新树的根，并将整个森林连成一棵树。考虑在树上做树形 DP。

注意到 a_u 的值域较大，而 n 的值域较小。定义如下状态：

接下来思考如何转移。假设当前结点为 u，子结点为 v。排列组合一下可以得到 3\times 3 = 9 种转移：

稍微整理如下：

询问相当于找最大的 x，使得 f_{0,x,0} \le S。二分查找即可。

具体实现参见代码。时间复杂度为 O(n^2+Q\log n)。

{\color{#00CD00}\text{代码}}

#include <bits/stdc++.h>
#define int long long
#define MIN(a, b) a = min(a, b)
using namespace std;
const int N = 1e3 + 5, inf = 1e18;
long long n, m, q, root = 0;
int a[N], sz[N], mi[N], vis[N];
vector<int> G[N];
void DFS(int u, int fa){
    vis[u] = true;
    for(int v: G[u]) if(v != fa) DFS(v, u);
}
int f[N][N][3];
//f[i][j][0/1/2]: 以 i 为根的子树中，有 j 个贡献，结点 i 不选/选了但无贡献/选了且有贡献的最小代价 
void dfs(int u, int fa){ //树形 DP 
    sz[u] = 1;
    f[u][0][0] = 0, f[u][0][1] = a[u];
    for(int v: G[u]){
        if(v == fa) continue;
        dfs(v, u);
        for(int i=sz[u]; i>=0; i--){
            for(int j=sz[v]; j>=0; j--){ //dp 转移 
                MIN(f[u][i+j][0], f[u][i][0] + min({f[v][j][0], f[v][j][1], f[v][j][2]}));
                MIN(f[u][i+j][1], f[u][i][1] + f[v][j][0]);
                MIN(f[u][i+j][2], f[u][i][2] + min(f[v][j][0], f[v][j][2]));
                MIN(f[u][i+j+1][2], min(f[u][i][1] + f[v][j][2], f[u][i][2] + f[v][j][1]));
                MIN(f[u][i+j+2][2], f[u][i][1] + f[v][j][1]);
            }
        }
        sz[u] += sz[v];
    }
}
signed main(){
    cin.tie(nullptr) -> sync_with_stdio(false);
    cin >> n >> m; a[root] = inf; //将虚根的代价设为无穷大，避免被选 
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=m; i++){
        int u, v; cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }
    for(int i=1; i<=n; i++) if(!vis[i]){ //将森林连城一棵树 
        G[root].push_back(i), DFS(i, root);
    }
    memset(f, 0x3f, sizeof(f)); dfs(root, -1);
    mi[n+1] = inf; //mi[i] 表示获得 i 个贡献的最小代价
    for(int i=n; i>=1; i--) mi[i] = min(mi[i+1], f[root][i][0]); 
    for(cin >> q; q --> 0;){
        int s; cin >> s;
        cout << upper_bound(mi+1, mi+1+n, s) - mi - 1 << "\n"; //二分查询答案 
    }
    return 0;
}