本文主要是介绍CQOI珠宝,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
CQOI珠宝
给一棵n个结点的树,给每个点安排一个正整数编号,使得相邻点具有不同的编号,编号的总和尽量小。
输入格式:
第一行:n(n<=50,000) 以下n-1行,每行两个数u,v(1<=u,v<=n),表示u 和v有一条边
输出格式:
仅一行,为最小编号和
样例输入:
8 1 2 1 31 41 55 65 75 8
样例输出:
11
数据范围:
30%的数据满足,n<=200; 60%的数据满足,n<=5000;
100%的数据满足,n<=50,000;
时间限制:
1000
空间限制:
512000
记忆化搜索搞treedp,f[i][j]表示i原点,权值为j时的最小和(包括自己和其子数)
//打题启示:以后边表的数组记得开两倍,千万别把边号和点号搞反,以后遇这种题treedp爆枚,算好复杂度,m别设太大
#include<bits/stdc++.h>
using namespace std;
const int m=10;
int n;
int de[100001];
int fir[100001];
int ne[100001];
int to[100001];
int fa[50001];
int son[50001][1001];
int sn[50001];
int f[50001][11];
int u,v,tot;
int root=1;
int num[2];
void add(int u,int v)
{
to[++tot]=v;ne[tot]=fir[u];fir[u]=tot;
}
void dfs(int no,int depth)
{
de[no]=depth;num[depth%2]++;
for(int i=fir[no];i;i=ne[i])
{
int tt=to[i];
if(tt==fa[no]) continue;
else
{
son[no][++sn[no]]=tt;
fa[tt]=no;
dfs(tt,depth+1);
}
}
}
int dp(int no,int xy)
{
if(f[no][xy]) return f[no][xy];f[no][xy]=xy;
if(sn[no]==0) return f[no][xy];
for(int i=fir[no];i;i=ne[i])
{
int tt=to[i];
if(tt==fa[no]) continue;
int rude=2e9;
for(int j=1;j<=m;j++)
{
if(j==xy) continue;
rude=min(rude,dp(tt,j));
}
f[no][xy]+=rude;
}
return f[no][xy];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(root,1);
int ans=2e9;
for(int i=1;i<=m;i++)
{
ans=min(ans,dp(root,i));
}
cout<<ans;
return 0;
}
/*
8
1 2
1 3
1 4
1 5
5 6
5 7
5 8
*/
#include<bits/stdc++.h>
using namespace std;
const int m=10;
int n;
int de[100001];
int fir[100001];
int ne[100001];
int to[100001];
int fa[50001];
int son[50001][1001];
int sn[50001];
int f[50001][11];
int u,v,tot;
int root=1;
int num[2];
void add(int u,int v)
{
to[++tot]=v;ne[tot]=fir[u];fir[u]=tot;
}
void dfs(int no,int depth)
{
de[no]=depth;num[depth%2]++;
for(int i=fir[no];i;i=ne[i])
{
int tt=to[i];
if(tt==fa[no]) continue;
else
{
son[no][++sn[no]]=tt;
fa[tt]=no;
dfs(tt,depth+1);
}
}
}
int dp(int no,int xy)
{
if(f[no][xy]) return f[no][xy];f[no][xy]=xy;
if(sn[no]==0) return f[no][xy];
for(int i=fir[no];i;i=ne[i])
{
int tt=to[i];
if(tt==fa[no]) continue;
int rude=2e9;
for(int j=1;j<=m;j++)
{
if(j==xy) continue;
rude=min(rude,dp(tt,j));
}
f[no][xy]+=rude;
}
return f[no][xy];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(root,1);
int ans=2e9;
for(int i=1;i<=m;i++)
{
ans=min(ans,dp(root,i));
}
cout<<ans;
return 0;
}
/*
8
1 2
1 3
1 4
1 5
5 6
5 7
5 8
*/
这篇关于CQOI珠宝的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!