P4395 [BOI2003]Gem 气垫车/P5765 [CQOI2005]珠宝

标签：ch const int P5765 BOI2003 P4395 dp define

P4395 [BOI2003]Gem 气垫车 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

类似于cf特色题

不能简单的（1，2）两个值进行考虑

 

 显然 1的编号为2,2的编号为3,其余都是1才是特殊情况

我们令dp[x][i]为x节点为i时，所能获得子树最小值

dp[x][i]=∑ (  min( dp[v][j]  (i!=j)  )

这是 i 不就可以有无穷多个值了吗？

实际上 i 枚举到 20或25就能找到全局最小值了,属于是cf特色题了

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   
#define popb pop_back  
#define fi first
#define se second
const int N=5e4+10;
//const int M=;
const int inf=0x3f3f3f3f;     
//const ll INF=0x3ffffffffffff;
int T,n,dp[N][30];
vector<int> g[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^48);ch=getchar();}
    return x*f;
}
void dfs(int x,int fa)
{
    for(int i=1;i<=20;i++) dp[x][i]=i;
    for(int v:g[x])
    {
        if(v==fa) continue;
        dfs(v,x);
        for(int i=1;i<=20;i++)
        {
            int minn=inf;
            for(int j=1;j<=20;j++)
                if(i!=j) minn=min(minn,dp[v][j]);
            dp[x][i]+=minn;
        }
    }
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
    n=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        g[u].pb(v),g[v].pb(u);
    }
    dfs(1,0);
    int ans=inf;
    for(int i=1;i<=20;i++) ans=min(ans,dp[1][i]);
    printf("%d",ans);
    return 0;
}

 

标签：ch,const,int,P5765,BOI2003,P4395,dp,define
From： https://www.cnblogs.com/Willette/p/17234188.html