题解 P4437 【[HNOI/AHOI2018]排列】

## [题意](https://blog.csdn.net/BeNoble_/article/details/79973942) 给你一个序列$a$ 定义$a$的一个排列$p$合法需要满足当$p[j]\le p[k]$时不存在$a_{p[j]}=p[k]$ 定义一个排列的权值是$\sum_{i=1}^n iw_{p[i]}$ 求最大权值 --- 你永远不会想到会在正式考试上看到原题$,$而且还在某校集训上讲过$???$ 原题链接[$Poj2054$](http://poj.org/problem?id=2054) --- ## 题解 ### 考虑转化 考虑到如果$a_j=k$那么$k$一定要排在$j$前面 可以理解为对于$j$来说$k$需要先选 考虑建出一个图$,$连边$k=a_j\to j$方向表示顺序 这样$[1,n]$每个点的入度都会是$1$ 如果有环那么就无解$,$否则这个图就是一棵以$0$为根树 如果是在树上的话$,$也就是说必须要先选父亲才能选儿子 对于一个点$i,$如果选到他的时间是$T$也就是说他在排列中的位置是$T,$那么他的贡献就是$Tw_i$ 这样我们就成功把这道题转化成那个[原题](http://poj.org/problem?id=2054)了~~但是这并没有什么用~~ ### 考虑怎么求最大值 考虑一种贪心 考虑一个当前权值最小的点$i$ $1.$如果$i$没有父亲$(fa[i]=0),$那么我们当前一定是选$i$ $2.$如果$i$有父亲$,$那么当$fa[i]$选了后我们一定会最先选$i$ 也就是说在最后的排列中$fa[i]$和$i$是挨在一块的 但是考虑到实际上多次合并后每个节点就是一个序列 考虑一个长度为$m_1$的序列$a$和一个长度为$m_2$的序列$b$ 考虑$ab$和$ba$两种合并后的序列的答案(假设当前在第$i$位) $$W_{ab}=\sum_{j=1}^{m_1}(i+j)w_{a_j}+\sum_{j=1}^{m_2}(i+j+m_1)w_{b_j}$$ $$W_{ba}=\sum_{j=1}^{m_2}(i+j)w_{b_j}+\sum_{j=1}^{m_1}(i+j+m_2)w_{a_j}$$ $$W_{ab}-W_{ba}=m_1W_b-m_2W_a$$ 如果$W_{ab}\gt W_{ba}\Rightarrow \frac{W_a}{m_1}\lt\frac{W_b}{m_2}$ 也就是平均权值小的放前面答案会更优 那么我们把平均权值作为合并后的新权值继续操作即可 计算答案的话就把答案拆开来计算 根据上面的式子可以得到把一个序列$b$放在一个序列$a$后面会产生独立的$W_b\times m_1$的贡献$,$边合并边求和就好了 每次取最小可以用堆实现 因为要修改权值~~所以你可以用set~~ 你可以用$pb\_ds$里面的带修改堆$,$或者你拿个东西做标记就好了 ``` #include<bits/stdc++.h> #define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i) #define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to) #define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; char ss[1<<17],*A=ss,*B=ss; inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;} template<class T>inline void sd(T&x){ char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48; while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y; } char sr[1<<21],z[20];int C=-1,Z; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} template<class T>inline void we(T x){ if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]='\n'; } const int N=5e5+5; typedef int arr[N]; typedef long long ll; struct Da{ int u,sz;ll w; inline bool operator<(const Da b)const{return w*b.sz>b.w*sz;} }; struct eg{int nx,to;}e[N]; int n,Cnt;arr fi,fa,Fa,sz,vis;ll ans,w[N];priority_queue<Da>q; void dfs(int u){vis[u]=1;++Cnt;go(u)if(vis[v]){puts("-1"),exit(0);}else dfs(v);} inline void add(int u,int v){static int ce=0;e[++ce]={fi[u],v},fi[u]=ce;} int gf(int x){return Fa[x]==x?x:Fa[x]=gf(Fa[x]);} int main(){ #ifndef ONLINE_JUDGE file("s"); #endif sd(n); fp(i,1,n)sd(fa[i]),add(fa[i],i); dfs(0);if(Cnt<=n)return puts("-1"),0; fp(i,0,n)Fa[i]=i,sz[i]=1; fp(i,1,n)sd(w[i]),q.push(Da{i,1,w[i]}); int u,p;Da s; while(!q.empty()){ s=q.top();q.pop(); if(sz[u=gf(s.u)]^s.sz)continue; Fa[u]=p=gf(fa[u]); ans+=w[u]*sz[p],w[p]+=w[u],sz[p]+=sz[u]; if(p)q.push(Da{p,sz[p],w[p]}); } printf("%lld\n",ans); return 0; } ```