题解 P4362 【[NOI2002]贪吃的九头龙】

· · 题解

这道题不难看出是一道树形DP的题目，但我在写题时突发奇想，如有不对，各位请指正。

我们在读题时可以发现这样一个问题，数据范围特别水。。。N <= 300而已。其实这样的大小可以说是DP的潜台词了，但作为一个从不按套路出牌的我，决定利用前缀和水过去。

我们将样例画出来后会发现可以将整棵树分成四部分：1，以最大的果实为根节点的自己；2，以最左边的二代子节点为根节点的第一子树；3，以中间的二代子节点为根节点的第二子树；4，以最右边的二代子节点为根节点的第三子树。

这样分开有些问题就一目了然了

问题瞬间简化为选择题，我们只需要考虑取min{父亲，第一子树和，第二子树和，第三子树和}，除非选择父亲节点，不然继续递归。

解释完样例后，我们可以将这个规律发扬。

发扬规律不难理解，但我们还面临一个问题就是大头吃K个果子，一旦K小于子树个数就有些麻烦。

为解决问题我们可以自己写一个min函数，原理可以参考快排，在这里不多加赘述。

不过尴尬的是虽然我说了这么多，但我自己写的代码还是树形DP的（毕竟这是突发奇想嘛，大家理解一下），这个想法的实现就留给读者自己思考了（好熟悉的话）。

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int _=305;

inline int read()
{
    char ch = '!';
    int z = 1 , num = 0;
    while(ch != '-' && (ch < '0' || ch > '9'))
        ch = getchar();
    if(ch == '-')
    {
        z = -1;
        ch = getchar();
    }
    while(ch <= '9' && ch >= '0')
    {
        num = (num << 3) + (num << 1) + ch - '0';
        ch = getchar();
    }
    return z * num;
}

int N , M , K , f[_][_][2] , tmp[_][2];
struct hand
{
    int to , next , w;
}e[_<<1];
int cnt , head[_];

void link(int u , int v , int w)
{
    e[++cnt] = (hand){v,head[u],w};
    head[u]=cnt;
}
void dfs(int u,int fa)
{
    f[u][0][0]=f[u][1][1]=0;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);
        memcpy(tmp,f[u],sizeof(tmp));
        memset(f[u],63,sizeof(f[u]));
        for(int j=0;j<=K;++j)
        {
            for(int t=0;t<=j;++t)
            {
                f[u][j][0]=min(f[u][j][0],min(f[v][t][0]+tmp[j-t][0]+(M==2)*e[i].w,f[v][t][1]+tmp[j-t][0]));
                f[u][j][1]=min(f[u][j][1],min(f[v][t][1]+tmp[j-t][1]+e[i].w,f[v][t][0]+tmp[j-t][1]));
            }
        }
    }
}
int main()
{
    N=read();M=read();K=read();
    if(N-K<M-1){puts("-1");return 0;}
    for(int i=1;i<N;++i)
    {
        int x=read(),y=read(),z=read();
        link(x,y,z);link(y,x,z);
    }
    memset(f,63,sizeof(f));
    dfs(1,1);
    printf("%d\n",f[1][K][1]);
    return 0;
}

有什么意见或者让我打脸的证明欢迎私信我（打我脸的仁兄轻一点）