P2016 战略游戏——树状DP的使用

题面

树状DP是给树状结构的题做动态规划 找最值，因此要造一个树结构，我们可以用vector数组存储每个结点连接的边 造一个树出来，然后通过dfs不断遍历每个结点，对每个结点进行放置人或者不放置人操作，递归到根节点输出答案

建树+找根节点

int n, a, b, z;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a >> b;
        ++a;
        for (int j = 1; j <= b; j++)
        {
            cin >> z;
            ++z;
            father[z] = 1;
            s[a].push_back(z);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (father[i] == 0)
        {
            root = i;
            break;
        }
    }

dfs遍历并且对每个结点进行操作

对每个结点放置与不放置两种状态分别赋为1和0 然后继续向下搜索 回归累加最小值

void dfs(int x)
{
    res[x][0] = 0;
    res[x][1] = 1;
    if (s[x].size() == 0)
        return;
    for (int i = 0; i < s[x].size(); i++)
    {
        int y = s[x][i];
        dfs(y);
        res[x][0] += res[y][1];
        res[x][1] += min(res[y][1], res[y][0]);
    }
}

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1700;
int res[N][2];
bool father[N];
int root;
vector<int> s[N];
void dfs(int x)
{
    res[x][0] = 0;
    res[x][1] = 1;
    if (s[x].size() == 0)
        return;
    for (int i = 0; i < s[x].size(); i++)
    {
        int y = s[x][i];
        dfs(y);
        res[x][0] += res[y][1];
        res[x][1] += min(res[y][1], res[y][0]);
    }
}
 
int main()
{
    int n, a, b, z;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a >> b;
        ++a;
        for (int j = 1; j <= b; j++)
        {
            cin >> z;
            ++z;
            father[z] = 1;
            s[a].push_back(z);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (father[i] == 0)
        {
            root = i;
            break;
        }
    }
    dfs(root);
    cout << min(res[root][0], res[root][1]);
}