2023.10.12-秋招-留学生-第三题-塔子哥的分糖果方案

TaZi SU @ 7 months ago

题面描述

塔子哥组织了一场小朋友的游戏，需要分发糖果以确保每根绳子的两端至少有一个小朋友开心。每个小朋友可以牵引多个同学，形成树形结构。通过合理分配糖果，目标是用最少的糖果让每个小朋友开心，从而实现快乐的游戏氛围。输入包含小朋友数量及其牵引关系，输出所需的最少糖果数。

思路：树形DP

定义 $f[i][j]$ 为以 $i$ 为结点的子树中，不放消防栓/放消防栓（ $j=0/1$ ）的最小个数

如果在第 $i$ 个结点放置消防栓，那么对于结点 $i$ 的所有子节点，都可以放置/不放置消防栓

则有$f[i][1]=\sum_{}^{}min(f[u][0],f[u][1]) (u\in {i|u是i的子节点})$

如果在第 $i$ 个结点不放置消防栓，那么对于结点 $i$ 的所有子节点，都必须要放置消防栓

则有 $f[i][0]=\sum_{}^{}f[u][1] (u\in {i|u是i的子节点})$

代码分析

这段代码的目的是在树形结构中找到最优的消防栓放置策略，以最小化需要的消防栓数量。以下是代码的详细分析：

变量与数据结构的初始化：
- const int N = 1510;：定义最大节点数为1510。
- int n;：小朋友数量，即树的节点数量。
- vector<vector<int>> g;：邻接表，用于存储树的结构。
- int f[N][2];：动态规划数组，其中 f[i][0] 表示不在节点 i 放置消防栓时的最小数量，f[i][1] 表示在节点 i 放置消防栓时的最小数量。
- int d[N];：入度数组，用于记录每个节点的入度，以便找到根节点。
深度优先搜索（DFS）函数：
- void dfs(int u)：递归函数，遍历树的节点。
  - 初始化 f[u][1] = 1，表示当前节点放置消防栓的数量。
  - 初始化 f[u][0] = 0，表示当前节点不放置消防栓时的数量。
  - 对于每个子节点 x，递归调用 dfs(x)。
  - 更新状态转移方程：如果放置消防栓，子节点可以选择放或不放；如果不放，则子节点必须放置。

C++

#include<bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>>g;
const int N=1510;
int f[N][2],d[N];
void dfs(int u)
{
    f[u][1]=1;f[u][0]=0;
    for(int &x:g[u])
    {
        dfs(x);
        f[u][1]+=min(f[x][0],f[x][1]);
        f[u][0]+=f[x][1];
    }
    
}
int main()
{
    cin>>n;
    g.resize(n);
    memset(d,0,sizeof d);
    int t,cnt;
    for(int i=0;i<n;i++)
    {
        scanf("%d:(%d)",&t,&cnt);
        while(cnt--)
        {
            int a;
            cin>>a;
            g[t].push_back(a);
            d[a]++;
        }
    }
    int root=0;
    while(d[root])root++;
    dfs(root);
    int res=min(f[root][0],f[root][1]);
    cout<<res<<endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    static int n;
    static List<List<Integer>> g;
    static final int N = 1510;
    static int[][] f = new int[N][2];
    static int[] d = new int[N];

    static void dfs(int u) {
        f[u][1] = 1;
        f[u][0] = 0;
        for (int x : g.get(u)) {
            dfs(x);
            f[u][1] += Math.min(f[x][0], f[x][1]);
            f[u][0] += f[x][1];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        g = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }
        Arrays.fill(d, 0);
        for (int i = 0; i < n; i++) {
            String[] data = sc.next().split(":");
            int t = Integer.parseInt(data[0]);
            int cnt = Integer.parseInt(data[1].substring(1, data[1].length() - 1));
            while (cnt-- > 0) {
                int a = sc.nextInt();
                g.get(t).add(a);
                d[a]++;
            }
        }
        int root = 0;
        while (d[root] > 0) {
            root++;
        }
        dfs(root);
        int res = Math.min(f[root][0], f[root][1]);
        System.out.println(res);
    }
}

Python

import re

n = int(input())
g = [[] for _ in range(n)]
N = 1510
f = [[0, 0] for _ in range(N)]
d = [0 for _ in range(N)]

def dfs(u):
    f[u][1] = 1
    f[u][0] = 0
    for x in g[u]:
        dfs(x)
        f[u][1] += min(f[x][0], f[x][1])
        f[u][0] += f[x][1]

for _ in range(n):
    data = re.findall(r'\d+', input())
    t = int(data[0])
    cnt = int(data[1])
    for i in range(2, 2 + cnt):
        a = int(data[i])
        g[t].append(a)
        d[a] += 1

root = 0
while d[root] > 0:
    root += 1

dfs(root)
res = min(f[root][0], f[root][1])
print(res)

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

动态规划

# Submissions

Accepted

Uploaded By

TaZi

1 solutions

题面描述

代码分析

Information

Status

Development

Support