【学术篇】SDOI2008 山贼集团
今天一月一号..
突然想安利一波我的中二的2017总结...
传送门1:codevs
传送门2:luogu
时限5s和1s的区别(你没看我传送门都给的大牛分站了)
现在不仅线筛.. 有负数的快读都打不对了..
来比较一下他们的区别?
inline int gn(int a=0,char c=0,int f=1){ for(;(c<48||c>57)&&c!='-';c=getchar());if(c=='-')f=-1,c=getchar(); for(;c>47&&c<58;c=getchar()) a=a*10+c-'0'; return a*f; } inline int gn(int a=0,char c=0,bool f=1){ for(;(c<48||c>57)&&c!='-';c=getchar());if(c=='-')f=-1,c=getchar(); for(;c>47&&c<58;c=getchar()) a=a*10+c-'0'; return a*f; } inline int gn(int a=0,char c=0,bool f=1){ for(;(c<48||c>57)&&c!='-';c=getchar());if(c=='-')f=-1; for(;c>47&&c<58;c=getchar()) a=a*10+c-'0'; return a*f; }
Emmmm 于是就愉快的残掉了..
好吧回到正题.
这个题网上的题解好少啊OvO毕竟bzoj有10道sdoi2008, 这题就属于被忽略的题目之一...
不知道为什么...
数据范围\(p<=12\)一眼状压...
我们可以用12位二进制表示一个集合...
这样定义状态\(f_{x,s}\)为第\(i\)个节点上安排集合\(s\)的状态...
这样的话\(s\)就是每个儿子和安排在该点的集合们的并集...
但是很多个儿子差集就不好取了, 考虑多叉树转二叉树...
然而似乎传统的左儿子右兄弟是不行的... 我们考虑另一种转化方式..
比如我们有一棵这样的树:
转成一棵抉择方案等价的树是这样的:
这里我们对于有多个子树的节点, 建立虚拟节点(注意:虚拟节点是不能安排集合的)
如果有好多子树就继续递归下去(比如如果1有2 3 4 5四个子树, 那么就在10的右儿子挂一个12, 然后把4 5分别放在12的左右儿子.
由于有些点不能放集合, 我们定义\(g_{x,s}\)表示在以\(x\)为根的子树中不在\(x\)节点安排集合时的最大价值.
这样我们就可以根据二叉树写出状态转移方程:
\[f_{x,s}=\left\{\begin{matrix}max\{g_{x,k}-cost_{s-k}\}+val_s (k\subseteq s),\; x<=n\\\\ g_{x,s},\; x>n\end{matrix}\right.\\g_{x,s}=max\{f_{l,k}+f_{r,s-k}\}(k\subseteq s)\]
根据这个状态转移方程推就行了...
不过好像是有些卡时间的...
我们可以预处理出某个集合的费用\(cost\)和价值\(val\)
然后枚举子集是有技巧的:
for(int k=s;k;k=(k-1)&s){ }
这样会快一点... 大约能把复杂度从\(4^n\)降到\(3^n\)左右...
不过要记得特殊处理空集(因为这样枚举的\(k\)不会到0)
就做完了...
代码(压常数版):
由于压了常数变得非常丑(本来写的也没多好看OvO)...
#include <cstdio> #include <cstdio> #include <cstring> #define ri register int const int N=204,P=4100,I=-1061109568; int f[N][P],g[N][P],du[N>>1]; int w[N][13],val[P],Val[P],cost[N][P]; int ch[2][N],n,nn,p,t; bool vis[N]; int a,b,s; inline int gi(int a=0,char c=0){ for(;c<48||c>57;c=getchar()); for(;c>47&&c<58;c=getchar())a=a*10+c-48;return a; } inline int gn(int a=0,char c=0,int f=1){ for(;(c<48||c>57)&&c!='-';c=getchar());if(c=='-')f=-1,c=getchar(); for(;c>47&&c<58;c=getchar()) a=a*10+c-'0'; return a*f; } inline int max(const int &a,const int &b){return a>b?a:b;} inline int min(const int &a,const int &b){return a<b?a:b;} struct edge{ int to,next; }e[N]; int v[N>>1],tot; inline void buildedge(const int &x,const int &y){ e[++tot].to=y; e[tot].next=v[x]; v[x]=tot; ++du[x]; e[++tot].to=x; e[tot].next=v[y]; v[y]=tot; ++du[y]; } void dfs1(int x){ int now=x; vis[x]=1; for(ri i=v[x];i;i=e[i].next){int y=e[i].to; if(!vis[y]){ if(!ch[0][now]) ch[0][now]=y; else if(du[x]==1) ch[1][now]=y; else ch[1][now]=++nn,now=nn,ch[0][now]=y; --du[y];--du[x]; dfs1(y); } } } int G(int x,int zt); int F(int x,int zt){ if(f[x][zt]>I) return f[x][zt]; if(x>n) return G(x,zt); f[x][zt]=Val[zt]-cost[x][zt]; for(ri z=zt;z;z=(z-1)&zt) f[x][zt]=max(f[x][zt],G(x,z)-cost[x][zt^z]+Val[zt]); return f[x][zt]; } int G(int x,int zt){ if(!ch[0][x]&&!ch[1][x]) return I; if(g[x][zt]>I) return g[x][zt]; if(!ch[1][x]) g[x][zt]=F(ch[0][x],zt); else if(!ch[0][x]) g[x][zt]=F(ch[1][x],zt); else{ for(ri z=zt;z;z=(z-1)&zt) g[x][zt]=max(g[x][zt],F(ch[0][x],z)+F(ch[1][x],zt^z)); g[x][zt]=max(g[x][zt],F(ch[1][x],0)+F(ch[1][x],zt)); } return g[x][zt]; } int main(){ nn=n=gi(); p=gi(); memset(f,192,sizeof(f)); memset(g,192,sizeof(g)); for(ri i=1;i<n;++i){ a=gi(),b=gi(); buildedge(a,b); } for(ri i=1;i<=n;++i) for(ri j=1;j<=p;++j) w[i][j]=gi(); t=gn(); for(ri i=1;i<=t;++i){ a=gn(),b=gi(),s=0; for(ri j=0;j<b;++j) s|=(1<<(gn()-1)); val[s]+=a; } dfs1(1); for(ri i=0;i<1<<p;++i){ for(ri j=i;j;j=(j-1)&i) Val[i]+=val[j]; for(ri j=1;j<=n;++j) for(ri k=1;k<=p;++k) if(i&(1<<(k-1))) cost[j][i]+=w[j][k]; } printf("%d\n",F(1,(1<<p)-1)); }