题解---洛谷P2230 [HNOI2002]Tinux系统

· · 题解

这是一道很水的黑题。

但是，本题的题意十分难懂。注意：样例输入是错的，最后一个4是多出来的。

整个题目的意思大概是：

一个节点最多可以有 k 条边连向儿子，每条边有一个权值 a_i ，一条边 (u,v) （ u 是父亲， v 是儿子）对答案的贡献是 v 子树内叶子节点的 个数² * a_i

其中，每个节点可以连出的边的权值是固定的，也就是说，每一个节点，它向儿子连边时，可以选择的边都是一样的。现在告诉你有 n 个叶子结点，问你最小的答案。(n<=1000,k<=1000)

思路很简单，就是一个记忆化搜索，f[x][y] 表示现在有 x 个叶子节点待填，已经连了 y-1 条边出去，当然对边权排序是必要的，因为显然，我们要保证最小的边下面跟的叶子节点最多。

然后转移也十分容易，对每条边，只有两种选择：

1.连叶子，直接加上 a_i

2.连非叶子节点，先加上这条边的贡献，然后在继续递归就可以了。

所以，我们只需要枚举第二种情况时，该节点下面放几个叶子节点就ok了

时间复杂度：O(nk)

代码：

#include<bits/stdc++.h>
using namespace std;
int n,k,f[1005][1005],a[1005];
int dfs(int x,int y)
{
    if(x==1)
    {
        f[x][y]=a[y];
        return f[x][y];
    }//只剩一个节点
    if(y==k)return f[x][y]=dfs(x,1)+a[y]*x*x;
    //只剩一条边，必须是连非叶子节点
    if(f[x][y])return f[x][y];
    f[x][y]=dfs(x-1,y+1)+a[y];//直接连叶子
    for(int i=2;i<x;i++)//枚举
    f[x][y]=min(f[x][y],dfs(x-i,y+1)+a[y]*i*i+dfs(i,1));
    return f[x][y];
}
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=k;i++)cin>>a[i];
    sort(a+1,a+k+1);
    printf("%d",dfs(n,1));
}