P5765 [CQOI2005]珠宝

xkcdjerry · 2021-05-10 23:08:49 · 题解

因为我菜便于理解这里先说一下我怎么想到用树 DP :

最优子结构：如果从下向上填的话，对于一个节点来说除了它的直接儿子之外，子树中的其它内容对其无用
次序：由于问题在树上，所以天然存在 dfs 序

那么树 DP 理论可行，由于父节点仍然需要记录子节点的数值以免重复，所以转移表应该长这个样子： f[x][y]=节点x填y时子树的最小和

转移方程就是这个：

f_{x,y}=\sum_{i \in sons[x]} \min(j \neq x:f_{i,j})

（其它题解给的第二维的都是 1~10 ，但是因为数据太水可以压缩到 1~4 ）

代码（记住，树 DP 必须要用 dfs ）：

#include <cstdio>
#include <vector>
using std::vector;
//代码里没有对索引 -1 所以虽然只有 1~4 也要开五个位置
#define MX 5 
#define N 50010
int f[N][MX];
bool vis[N];
vector<int> e[N];
int n;
void dfs(int o)
{
    //处理出 o 节点所有填的值的最小值
    vis[o]=true;
    for(int i=1;i<MX;i++) f[o][i]=i;
    for(vector<int>::iterator i=e[o].begin();i!=e[o].end();i++)
    {
        if(!vis[*i])
        {
            dfs(*i);
            for(int j=1;j<MX;j++)
            {
                int mn=0x3f3f3f3f;
                for(int k=1;k<MX;k++)
                    if(k!=j&&f[*i][k]<mn)
                        mn=f[*i][k];
                f[o][j]+=mn;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1);
    int mn=0x3f3f3f3f;
    for(int i=1;i<MX;i++) if(f[1][i]<mn) mn=f[1][i];
    printf("%d",mn);
    return 0;
}

开了 O2 之后排到最优解前三名（在文章提交时）