NOI2018 模拟 T2

NOI2018 模拟 T2

​​ 题意：求选出树上k个点 使得sigma a[i]-a[i-1]最大 a[i]-a[i-1]表示两个点 树上距离

容易发现k=n的时候 所有边长*2-直径就是我们要的 那么k< n的时候我们类似虚树dp一下即可

设dp[i][j][0/1/2]表示当前在i子树选了j个点我子树内有0,1,2个直径的端点我的最小代价是多少

转移见方程～

#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=3300;struct node{ int y,next,z;}data[N<<1];int dp[N][N][3],ans=0x3f3f3f3f,n,k,num,h[N],size[N];inline void mn(int &x,int v){x=min(x,v);}inline void dfs(int x,int fa){ size[x]=1;dp[x][1][0]=dp[x][1][1]=0; for (int owo=h[x];owo;owo=data[owo].next){ int y=data[owo].y;if (y==fa) continue; dfs(y,x);int z=data[owo].z; for (int i=size[x];~i;--i){ for (int j=size[y];~j;--j){ if (i+j>k) continue; mn(dp[x][i+j][0],dp[x][i][0]+dp[y][j][0]+(z<<1)); mn(dp[x][i+j][1],dp[x][i][1]+dp[y][j][0]+(z<<1)); mn(dp[x][i+j][1],dp[x][i][0]+dp[y][j][1]+z); mn(dp[x][i+j][2],dp[x][i][1]+dp[y][j][1]+z); mn(dp[x][i+j][2],dp[x][i][0]+dp[y][j][2]+(z<<1)); mn(dp[x][i+j][2],dp[x][i][2]+dp[y][j][0]+(z<<1)); } }size[x]+=size[y]; }ans=min(ans,min(dp[x][k][0],min(dp[x][k][1],dp[x][k][2])));}int main(){ freopen("2.in","r",stdin); n=read();k=read();memset(dp,0x3f,sizeof(dp)); for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。