A simple Blog for wyx I've been down the bottle hoping.
BZOJ 1369: [Baltic2003]Gem 树形dp
发表于: | 分类: Oi | 评论:0 | 阅读:76

第一次想的太少了……直接分层01做的……
错了之后马上就意识到了不对
我们可以通过利用大量的子树来逼迫一个点选2,3……
发现手画4都不太好画出来……

我们大胆猜测最多就能选10
然后乖乖的树形$dp$就行了
不知道$0ms$什么算法……TAT

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define N 100000+5
#define M 200000+5
using namespace std;
const int inf = 0x7fffff;
int head[N];

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

struct graph
{
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];

inline void add(int x,int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y);
    head[x] = cnt;
    edge[++cnt] = graph(head[y],x);
    head[y] = cnt;
}

int f[N][22];

void DFS(int x,int fa)
{
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa)
            DFS(edge[i].to,x);
    for(int j = 1; j <= 10; ++ j)
        f[x][j] = j;
    for(int j = 1; j <= 10; ++ j)
    {
        for(int i=head[x];i;i=edge[i].next)
        {
            int tmp = inf;
            if(edge[i].to!=fa)
            {
                for(int k = 1; k <= 10 ; ++ k)
                    if(j ^ k)
                        tmp = min(f[edge[i].to][k],tmp);
                f[x][j] += tmp;
            }
            
        }
    }
                
}

int main()
{   
    int n = read();
    for(int i=1;i<n;++i)
    {
        int x = read(),y = read();
        add(x,y);
    }
    DFS(1,1);
    int ans = inf;
    for(int i=1;i<=10;++i)
        ans = min(ans,f[1][i]);
    cout<<ans;
}


Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP