自动搬运

查看原文

来自洛谷，原作者为

	ran_qwq debug 深入思考 只靠样例与自己！

搬运于2025-08-24 23:09:37，当前版本为作者最后更新于2025-02-10 20:35:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

下文的 $l_i$ 表示题目的 $k_i$。

数据范围提示也太明显了吧。

注意到 $\sum l_i\cdot s\le10^7$，一个 $O(\sum l_i\cdot s)$ 的 dp 呼之欲出：$f_{i,j,k,0/1}$ 表示第 $i$ 题第 $j$ 个 subtask，总分为 $k$，这道题目前有没有得分是否可行。

转移几种情况：

• 当前是第一个 subtask：
  • 不拿分，$f_{i,1,k,0}\leftarrow f_{i-1,l_{i-1},k,1}$。
  • 拿分，$f_{i,1,k,1}\leftarrow f_{i-1,l_{i-1},k-c_{i,1},1}$。
• 当前不是第一个 subtask：
  • 不拿分：
    • 这道题之前没拿过分，$f_{i,j,k,0}\leftarrow f_{i,j-1,k,0}$。
    • 这道题之前拿过分，$f_{i,j,k,1}\leftarrow f_{i,j-1,k,1}$。
  • 拿分：
    • 这道题之前没拿过分，$f_{i,j,k,1}\leftarrow f_{i,j-1,k-c_{i,j},0}$。
    • 这道题之前拿过分，$f_{i,j,k,1}\leftarrow f_{i,j-1,k-c_{i,j},1}$。

需要输出方案，dp 数组可以记录“这道题当前拿不拿分”和“这道题之前有没拿过分”，构造时不断往前跳。

直接开 vector 会 MLE，需要开一维数组 dp。

int n,m,l[N],sl[N]; pii f[N*210]; vi c[N]; vi as[N];
il int gt(int x,int y,int z,int p) {return (m+1)*2*(sl[x-1]+y)+z*2+p;}
void prt(int x,int y,int z,int p) {
	if(!x) return;
	auto [s,t]=f[gt(x,y,z,p)];
	int u=x,v=y-1; if(!v) u--,v=l[u];
	if(s==1) prt(u,v,z,t);
	else as[x].pb(y),prt(u,v,z-c[x][y],t);
}
void QwQ() {
	n=rd(),m=rd(),sl[0]=1;
	for(int i=1;i<=n;i++) {
		l[i]=rd(),c[i].resize(l[i]+1),sl[i]=sl[i-1]+l[i];
		for(int j=1;j<=l[i];j++) c[i][j]=rd();
	}
	f[gt(0,0,0,1)]={-1,-1};
	for(int i=1;i<=n;i++) {
		for(int k=0;k<=m;k++) {
			if(f[gt(i-1,l[i-1],k,1)].fir) f[gt(i,1,k,0)]={1,1};
			if(k>=c[i][1]&&f[gt(i-1,l[i-1],k-c[i][1],1)].fir) f[gt(i,1,k,1)]={2,1};
		}
		for(int j=2;j<=l[i];j++) for(int k=0;k<=m;k++) {
			if(f[gt(i,j-1,k,0)].fir) f[gt(i,j,k,0)]={1,0};
			if(f[gt(i,j-1,k,1)].fir) f[gt(i,j,k,1)]={1,1};
			else if(k>=c[i][j])
				if(f[gt(i,j-1,k-c[i][j],0)].fir) f[gt(i,j,k,1)]={2,0};
				else if(f[gt(i,j-1,k-c[i][j],1)].fir) f[gt(i,j,k,1)]={2,1};
		}
	}
	if(!f[gt(n,l[n],m,1)].fir) puts("No");
	else {
		puts("Yes"),prt(n,l[n],m,1);
		for(int i=1;i<=n;i++,puts("")) {
			wr(as[i].size(),"\n"),reverse(as[i].begin(),as[i].end());
			for(int j:as[i]) wr(j," ");
		}
	}
}