差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/09/05 16:55]
jxm2001
+++ 2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/10/04 17:00] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-===== G. Ball =====
+===== H. travel =====
 ==== 题意 ====
-给定一个斜坡，有 $n$ 个洞。再给定 $m$ 个球，依次抛球，每次抛球可以决定球的初始下落位置，然后球从斜坡向下运动。
+给定一棵点权树，从树上选三条不相交的路径，每条路径的权值定义为路径上的点权和，要求最大化三条路径权值和。
-如果球遇到空洞则将该洞填补，否则向下一个洞运动。如果球没有遇到任何空洞，则出界。问恰好出界 $k$ 个球的方案数。
 ==== 题解 ====
-设 $f(i,j)$ 表示 $i$ 个洞投 $j$ 个球且没有球出界的方案数。$g(i,j)$ 表示 $i$ 个洞投 $j$ 个球且所有洞都被填满的方案数。
+设 $\text{dp}(u,0/1/2,i)$ 表示只考虑 $u$ 的子树，结点 $u$ 的状态为 $0/1/2$ 时，已经选中了 $i$ 条链此时的最大路径权值和。
-枚举终态时从斜坡自下向上第一个空洞的位置 $i$，于是斜坡被分成两段，上段斜坡 $[i+1,n]$ 所有球一定不能出界，否则位置 $i$ 将不是空洞。
+我们需要维护一条正在生成的链，这条链不包含在已经选中的 $i$ 条链当中，如果 $u$ 状态为 $0$ 表示 $u$ 不在生成链中。
-下段斜坡 $[1,i-1]$ 一定全部被填满，且为保证有 $k$ 个球出界，一定恰好有 $i-1+k$ 个球投向下段斜坡。
+如果 $u$ 状态为 $1$ 表示 $u$ 在生成链中且 $u$ 只有一个儿子在生成链中， $u$ 状态为 $2$ 表示 $u$ 在生成链中且 $u$ 有两个儿子在生成链中。
-$$
+考虑状态转移，利用生成链的合并，不难有
-\text{ans}\gets \sum_{i=1}^{n} g(i-1,i-1+k)f(n-i,m-i-k+1){m\choose i-1+k}
-$$
-还要考虑终态没有空洞的情况
 $$
-\text{ans}\gets [m=n+k]g(n,m)
+\text{dp}(u,0,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,0,j)\\
+\text{dp}(u,1,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,1,j)+a_u\\
+\text{dp}(u,1,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,0,j)\\
+\text{dp}(u,2,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,1,j)\\
+\text{dp}(u,2,i+j)\gets \text{dp}(u,2,i)+\text{dp}(v,0,j)
 $$
-接下来考虑计算 $f(i,j),g(i,j)$。对 $f(i,j)(i\ge j)$，可以枚举有 $k$ 个球被抛向位置 $i$，不难发现剩下 $j-k$ 个球对应方案 $f(i-1,j-k)$。
+注意上式的 $\gets$ 表示取最大值，另外为了防止选中复数条从 $v$ 生成的链，需要开一个临时数组存储中间量。
-证明：不难发现交换投球顺序不影响终态，于是不妨假设这 $k$ 个球是最后投的。
+初始状态为 $\text{dp}(u,1,0)=a_u$，最后转移完要考虑将正在生成的链转化为已经选中的链，于是有
-由于前 $j-k$ 个球投完剩下 $i-j+k\ge k$ 个洞，于是 $k$ 个球可以全部进洞，证毕。最终有
 $$
-f(i,j)=\sum_{k=0}^j f(i-1,j-k){j\choose k}
+\text{dp}(u,0,i)\gets \max(\text{dp}(u,1,i-1),\text{dp}(u,2,i-1))
 $$
-对 $g(i,j)(i\le j)$，可以枚举最后一个球的进洞位置，同样可以把斜坡分两段，顺便考虑一下最后一个球出界的情况，于是有
+最终答案为 $\text{dp}(1,0,3)$，时间复杂度 $O(nk^2)$，其中 $k$ 表示最多能选中的链的个数。
-$$
+[[http://tokitsukaze.live/2018/07/24/2018niuke2.H/|参考资料]]
-g(i,j)=\sum_{k=0}^{i-1}\left(f(k,k)g(i-k-1,j-k-1){j-1\choose k}(k+1)\right)+g(i,j-1)i
-$$
-于是可以 $O\left(n^2m\right)$ 预处理，$O(n)$ 处理每个询问。
 <hidden 查看代码>
 <code cpp>
-const int MAXN=505,MAXM=1e3+5,mod=998244353;
+const int MAXN=4e5+5,MAXK=4;
-int f[MAXN][MAXM],g[MAXN][MAXM],C[MAXM][MAXM];
+struct Edge{
-void Init(){
+	int to,next;
-	C[0][0]=1;
+}edge[MAXN<<1];
-	_for(i,1,MAXM){
+int a[MAXN],head[MAXN],edge_cnt;
-		C[i][0]=1;
+LL dp[MAXN][3][MAXK],tmp[3][MAXK];
-		_rep(j,1,i)
+void Insert(int u,int v){
-		C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
+	edge[++edge_cnt]=Edge{v,head[u]};
-	}
+	head[u]=edge_cnt;
-	f[0][0]=g[0][0]=1;
+}
-	_for(i,1,MAXN){
+void Max(LL &a,LL b){
-		f[i][0]=1;
+	if(b>a)
-		_rep(j,1,i){
+	a=b;
-			_rep(k,0,j)
+}
-			f[i][j]=(f[i][j]+1LL*C[j][k]*f[i-1][j-k])%mod;
+void dfs(int u,int fa){
-		}
+	dp[u][1][0]=a[u];
-		_for(j,i,MAXM){
+	for(int i=head[u];i;i=edge[i].next){
-			_for(k,0,i)
+		int v=edge[i].to;
-			g[i][j]=(g[i][j]+1LL*f[k][k]*g[i-k-1][j-k-1]%mod*C[j-1][k]%mod*(k+1))%mod;
+		if(v==fa)continue;
-			g[i][j]=(g[i][j]+1LL*g[i][j-1]*i)%mod;
+		dfs(v,u);
+		_for(i,0,3)_for(j,0,MAXK)
+		tmp[i][j]=dp[u][i][j];
+		_for(i,0,MAXK)_for(j,0,MAXK-i){
+			Max(tmp[0][i+j],dp[u][0][i]+dp[v][0][j]);
+			Max(tmp[1][i+j],dp[u][0][i]+dp[v][1][j]+a[u]);
+			Max(tmp[1][i+j],dp[u][1][i]+dp[v][0][j]);
+			Max(tmp[2][i+j],dp[u][1][i]+dp[v][1][j]);
+			Max(tmp[2][i+j],dp[u][2][i]+dp[v][0][j]);
 		}
+		_for(i,0,3)_for(j,0,MAXK)
+		dp[u][i][j]=tmp[i][j];
 	}
+	_for(i,1,MAXK)
+	Max(dp[u][0][i],max(dp[u][1][i-1],dp[u][2][i-1]));
 }
-int main(){
+int main()
-	Init();
+{
-	int T=read_int();
+	int n=read_int();
-	while(T--){
+	_rep(i,1,n)
-		int n=read_int(),m=read_int(),k=read_int(),ans=0;
+	a[i]=read_int();
-		for(int i=0,t=min(n,m-k+1);i<t;i++)
+	_for(i,1,n){
-		ans=(ans+1LL*g[i][i+k]*f[n-i-1][m-i-k]%mod*C[m][i+k])%mod;
+		int u=read_int(),v=read_int();
-		if(m==n+k)
+		Insert(u,v);
-		ans=(ans+g[n][m])%mod;
+		Insert(v,u);
-		enter(ans);
 	}
+	dfs(1,0);
+	enter(dp[1][0][3]);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具