Flash 解题报告

Flash

Description

给你一颗树,需要把每个点染色,每个点染色时间为\(t_i\),要求同时染色的点的集合为树的独立集,最小化染色结束时间之和。

其实题面蛮有趣的♂

HINT

\(n\le 2000,t\)为整数


靠想象力吧,而且感觉这个题可以再优化优化状态之类的..

要先猜出一个结论,保证最优解的情况下每个点开始染色时间集合是有限的,具体的,这个集合大小为\(O(n)\),即每个点为根的到其他每个点路径上的点权和。

然后一个树形dp就行了

\(dp_{i,j}\)代表子树\(i\)以时间\(j\)开始的最小值

从儿子转移的时候,分两种,一种儿子在它后面染,一种在前面染,分别维护一下前缀最大or最小值,然后二分一下就可以了。


Code:

#include <cstdio>
#include <algorithm>
#define ll long long
const int N=2010;
int head[N],to[N<<1],Next[N<<1],cnt;
void add(int u,int v)
{
to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
using std::min;
const ll inf=1ll<<45;
ll dis[N][N],fpre[N][N],fsuc[N][N],dp[N][N],cost[N];
int n;
void dfs1(int now,int fa,ll *dis)
{
dis[now]=dis[fa]+cost[now];
for(int v,i=head[now];i;i=Next[i])
if((v=to[i])!=fa)
dfs1(v,now,dis);
}
void dfs(int now,int fa)
{
for(int i=1;i<=n;i++) dp[now][i]=dis[now][i];
for(int v,i=head[now];i;i=Next[i])
if((v=to[i])!=fa)
{
dfs(v,now);
for(int j=1;j<=n;j++)
{
ll mi=inf;
mi=min(mi,fpre[v][std::upper_bound(dis[v]+1,dis[v]+1+n,dis[now][j]-cost[now])-dis[v]-1]);
mi=min(mi,fsuc[v][std::lower_bound(dis[v]+1,dis[v]+1+n,dis[now][j]+cost[v])-dis[v]]);
if(mi<inf&&dp[now][j]!=inf) dp[now][j]+=mi;
else dp[now][j]=inf;
}
}
fpre[now][0]=fsuc[now][n+1]=inf;
for(int i=1;i<=n;i++) fpre[now][i]=min(fpre[now][i-1],dp[now][i]);
for(int i=n;i;i--) fsuc[now][i]=min(fsuc[now][i+1],dp[now][i]);
}
int main()
{
scanf("%d",&n);
for(int u,v,i=1;i<n;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
for(int i=1;i<=n;i++) scanf("%lld",cost+i);
for(int i=1;i<=n;i++)
{
dfs1(i,0,dis[i]);
std::sort(dis[i]+1,dis[i]+1+n);
}
dfs(1,0);
printf("%lld\n",fpre[1][n]);
return 0;
}

2019.1.5

上一篇:redis设置开机自启


下一篇:octave基本指令1