题解：P6499 [COCI2016-2017#2] Burza

Carey_chen · 2024-12-07 15:05:54 · 题解

Solution

这是一道不容易独立思考出来的状态压缩动态规划题。

考虑转化题意为：

有一棵树，求能不能在 1 \sim k（根节点为第 0 层）上的每一层标记一个点和它的整颗子树，使得第 k 层中的每个节点都被标记过。

显然这种可行的情况 (k^2 +1 = n) 需要标记的节点最多：

因此，当 k > \sqrt{n} 时一定可行。只需要考虑 k \leq \sqrt{n} 的情况。

定义 dp_{i, S} 为是否存在覆盖了第 k 层中的前 i 个节点，并且集合 S 中的每一层都标记过的情况。

最后判断覆盖第 k 层中的每个结点的情况是否存在即可。

Code

#include <bits/stdc++.h>

using namespace std;

const int M = (1 << 20) + 5;
vector<int> G[410];
int cnt = 0, n, k;
int l[410], r[410];
bool dp[410][M];

int p[410];

vector<int> T;
void dfs(int u = 1, int pre = -1, int dep = 0)
{
    p[u] = dep;
    if(dep == k)
    {
        cnt++;
        l[u] = r[u] = cnt;
        T.push_back(u);
        return;
    }

    l[u] = 1e9;
    r[u] = -1e9;

    for(auto v : G[u])
    {
        if(v != pre)
        {
            dfs(v, u, dep + 1);
            l[u] = min(l[u], l[v]);
            r[u] = max(r[u], r[v]);
        }
    }

    if(u != 1 && l[u] != 1e9 && r[u] != -1e9)
    {
        T.push_back(u);
    }
}

int main()
{
    scanf("%d %d", &n, &k);

    if(k > sqrt(n))
    {
        printf("DA\n");
        return 0;
    }

    for(int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs(1);
//  printf("%d \n", cnt);
//    for(auto i : T)
//    {
//      printf("%d %d %d\n", i, l[i], r[i]);
//    }

    int N = (1 << k) - 1;
    dp[0][0] = true;
    for(int i = 0; i <= cnt; i++)
    {
        for(int S = 0; S <= N; S++)
        {
            if(dp[i][S] == true)
            {
                //printf("  %d %d\n", i, S);
                for(auto j : T)
                {
                    if(!((S >> (p[j]-1)) & 1) && i + 1 == l[j])
                    {
                        //printf("    %d %d\n", l[j], r[j]);
                        dp[r[j]][S | (1 << (p[j]-1))] |= dp[i][S];
                    }
                }
            }
        }
    }
    //printf("%d %d", cnt,N);
    bool ans = false;
    for(int i = 0; i <= N; i++)
    {
        ans |= dp[cnt][i];
    }
    printf(ans ? "DA\n" : "NE\n");

    return 0;
}