P1552 [APIO2012]派遣
标签：int ace png div 技术 main inf 删除 wap
因为限制了编号，所以直接逆序就是自底而上，然后就是树形DP合并节点了，然后用可并堆贪心的删除节点，每次更新节点答案
#includeusing namespace std;
const int bow=100100;
int n,m,d[bow],lc[bow],rc[bow],f[bow],size[bow],sum[bow];
long long ans;
struct node{int sj,xs,ld;}num[bow];
int merge(int x,int y)
{
if(!x||!y)return x+y;
if(num[x].xsnum[y].xs)swap(x,y);
rc[x]=merge(rc[x],y);
if(d[lc[x]]d[rc[x]])swap(lc[x],rc[x]);
d[x]=d[rc[x]]+1;
return x;
}
int main()
{
cin>>n>>m;
for(int i=1;i)
{
cin>>num[i].sj>>num[i].xs>>num[i].ld;
ans=max(ans,1ll*num[i].ld);
size[i]=1;sum[i]=num[i].xs;f[i]=i;
}
for(int i=n;i>=1;i--)
{
int ssj=num[i].sj;
f[ssj]=merge(f[i],f[ssj]);
size[ssj]+=size[i];sum[ssj]+=sum[i];
while(sum[ssj]>m)
{
sum[ssj]-=num[f[ssj]].xs;
f[ssj]=merge(lc[f[ssj]],rc[f[ssj]]);
size[ssj]--;
}
ans=max(ans,1ll*num[ssj].ld*size[ssj]);
}
coutans;
}
P1552 [APIO2012]派遣
标签：int ace png div 技术 main inf 删除 wap
原文地址：https://www.cnblogs.com/SFWR-YOU/p/11514959.html
评论