bzoj4182 Shopping 购物 点分治+树形多重背包+dfs序+单调队列优化

本文主要是介绍bzoj4182 Shopping 购物 点分治+树形多重背包+dfs序+单调队列优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：传送门（权限题）

大毒瘤QAQ
发现买过物品的商店构成一个联通块，所以钦定一个根，让所有买过物品的商店到根的路径上的商店都是买过物品的商店。
然后在上面跑树形背包，子状态设计：
$dp[i][j]$表示选到$i$号节点，已经花了$j$块钱，所能达到的最大喜爱度。
用dfs实现的树形dp会TLE，考虑用dfs序来优化：
按照dfs序优化的套路，分不选当前节点和选当前节点两种情况。
倒序枚举dfs序，
当不选当前节点时，说明整棵子树都不能选，这个时候就从不属于这棵子树的dfs序最小的节点推过来。
用这个图来说明：

如果选当前节点，假设当前节点的dfs序为$i$，就从dfs序为$i+1$的节点推到这个节点。
这里dfs序为$i+1$的节点和dfs序为i的节点在同一个联通块中qwq，因此正确性珂以保证。
用这张图来说明：

用dfs序优化完，发现时间复杂度仍然不对，只是优化了常数。
据毒瘤czh所说多重背包珂以单调队列优化。
考虑这样一个经典的多重背包方程（$w[i]$表示物品重量，$v[i]$表示物品价值）：
$dp[j]=min(dp[j-w[i]\ast k]+v[i]\ast k)$
令$a=j/w[i],b=j$%$w[i]$，则方程珂以写成（边界条件略去）：
$dp[j]=min(dp[k\ast w[i]+b]+v[i]\ast (a-k))$
分离变量和不变量，珂以得到：
$dp[j]=min(dp[a\ast k+b]-v[i]\ast k)+v[i]\ast a$
对于$min$里面的部分，维护一个单调队列，这样每次就珂以$O(1)$推出。

注：这样每次需要枚举$mod$ $w[i]$的余数和商，看起来多了一重循环，但是不难发现余数与商所组成的数与直接枚举是一一对应的，所以不会影响复杂度。而单调队列则免去了决策点的寻找，所以总体优化掉了一个$O(n)$。

但是这样时间复杂度仍然是$O(n^{2}m)$，还是过不了qwq。
思考这道题的本质，因为所有选出的点都是一个联通块，所以不可能根不选，选出的其他点分布在两个子树中qwq。
所以每次找树的重心，跑点分治，每次能把规模降到原来的一半，因此最终时间复杂度$O(nmlogn)$。

代码

//yu xing chen xiao mei mei
//#pragma GCC optimize (3)
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#define re register int
#define rl register ll
using namespace std;
typedef long long ll;
int read() {re x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-')    f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
inline void write(int x) {if(x>9)	write(x/10);putchar(x%10+'0');
}
const int Size=505;
const int Maxn=4005;
namespace I_Love {int n,m,cnt,w[Size],c[Size],d[Size],head[Size];
struct Edge {int u,v,next;
} G[Size<<1];
void AddEdge(int u,int v) {G[++cnt].u=u;G[cnt].v=v;G[cnt].next=head[u];head[u]=cnt;
}
int ans,sum,root,maxp[Size],siz[Size];
bool vis[Size];
void getrt(int x,int fa) {//找树的重心 siz[x]=1;maxp[x]=0;for(int i=head[x]; i; i=G[i].next) {int nxt=G[i].v;if(!vis[nxt] && nxt!=fa) {getrt(nxt,x);siz[x]+=siz[nxt];if(siz[nxt]>maxp[x]) {maxp[x]=siz[nxt];}}}maxp[x]=max(maxp[x],sum-siz[x]);if(maxp[x]<maxp[root])	root=x;
}
int tim,dfn[Size];
void dfs(int x,int fa) {//求出dfs序和每个节点的子树大小 dfn[++tim]=x;siz[x]=1;for(int i=head[x]; i; i=G[i].next) {int nxt=G[i].v;if(!vis[nxt] && nxt!=fa) {dfs(nxt,x);siz[x]+=siz[nxt];}}
}
int dp[Size][Maxn],Queue[Maxn];
#define calc(pos) dp[i+1][j+Queue[pos]*c[x]]+(k-Queue[pos])*w[x]
void solve(int x) {vis[x]=true;tim=0;dfs(x,0);memset(dp[tim+1],0,sizeof(dp[tim+1]));for(re i=tim; i; i--) {int x=dfn[i];//不选的情况 for(re j=0; j<=m; j++) {dp[i][j]=dp[i+siz[x]][j];}//选的情况 for(re j=0; j<c[x]; j++) {	//枚举余数 int hd=1,tl=0;for(re k=0; k*c[x]+j<=m; k++) {		//枚举商 while(hd<=tl && Queue[hd]<k-d[x])	hd++;if(hd<=tl)	dp[i][j+k*c[x]]=max(dp[i][j+k*c[x]],calc(hd));while(hd<=tl && dp[i+1][j+k*c[x]]>=calc(tl))	tl--;Queue[++tl]=k;}}}//把所有经过根的情况取最大值 for(re i=1; i<=m; i++) {if(dp[1][i]>ans) {ans=dp[1][i];}}for(int i=head[x]; i; i=G[i].next) {int nxt=G[i].v;if(!vis[nxt]) {root=0;sum=siz[nxt];getrt(nxt,x);solve(root);}}
}
inline void clear() {tim=ans=root=cnt=0;memset(head,0,sizeof(head));memset(vis,0,sizeof(vis));maxp[0]=1e9;
}
void Kutori() {
//	freopen("1.in","r",stdin);int T=read();while(T--) {clear();n=read();m=read();for(re i=1; i<=n; i++)	w[i]=read();for(re i=1; i<=n; i++)	c[i]=read();for(re i=1; i<=n; i++)	d[i]=read();for(re i=1; i<n; i++) {int u=read();int v=read();AddEdge(u,v);AddEdge(v,u);}dfs(1,0);sum=n;getrt(1,0);solve(root);write(ans);putchar(10);}
}}
int main() {I_Love::Kutori();return 0;
}

这篇关于bzoj4182 Shopping 购物 点分治+树形多重背包+dfs序+单调队列优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---