自动搬运

查看原文

来自洛谷，原作者为

	s_r_f 这里是一个只会背板和fst的蒟蒻

搬运于2025-08-24 22:23:27，当前版本为作者最后更新于2020-08-07 19:05:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这个题实际上是个$NOIP$难度的题$,$不过出题人放到了$WC$的$T3,$题面看起来很劝退$,$代码也难写$,$数据范围也出锅了$,$所以没什么人过$.$

为了方便描述$,$

令$L=\max(T-\sum\limits_{i=1}^m s_i,0),$即满足每类学科达到条件的情况下额外需要的学分$,$数据范围保证了$0\leq L\leq 40.$

令$P$为所有的限制涉及到的课程总数$,$数据范围保证了$0\leq P\leq 12.$

subtask1 : $P=0$

对于每类课程$,$相当于我们要对一些体积为$1,2,3$的物品做背包$,$查询体积为$s_i,s_i+1,s_i+2,...s_i+L$的最小价值$,$最后跑一个$O(M*L^2)$的背包合并$.$

那么我们直接跑背包就可以以$O(N^2)$的复杂度解决$,$但是太慢了$.$

如果体积只有$1,$我们可以直接排序贪心$.$

如果体积只有$\{1,2\},$那么我们按照奇偶性分类排序贪心即可$,$具体的实现见下文$.$

上述贪心可以$O(n\log n)$的复杂度预处理并$O(1)$查询某个体积的结果$.$

然后体积集合变成了$\{1,2,3\},$我们就枚举$3$的使用次数$,$然后查询对$\{1,2\}$的贪心结果即可$.$

那么我们就可以以$O($ 查询体积 $)$的复杂度回答一个单点询问$.$

贪心计算的复杂度为$O(N\log N+NL),$总复杂度$O(N\log N+NL+M\times L^2),$

subtask2: $P\leq 12$

对于限制没有涉及到的情况$,$把需要的解都贪心计算出并记录下来$,$并把限制没有涉及到的类别的$dp$数组先计算出来$,$复杂度$O(N\log N+NL+M\times L^2)$

剩下的还没确定的类别有$O(P)$个$,$把这$O(P)$个类别除去限制涉及到的部分拿出来贪心并记录答案$.$

$O(2^P)$枚举限制涉及到的课程的选取情况$,$然后对每个情况$,$合并$O(P)$个$DP$数组即可$,$复杂度$O(2^PPL^2)$

总复杂度$O(N\log N+NL+M\times L^2+2^PPL^2)$

代码 $:$

inline void upd(int &x,int y){ y < x ? x = y : 0; }
const int N = 500005,M = 50005,K = 70,INF = 2e8;
struct Data{
	int v1[N],v3[N],v20[N],v21[N],l1,l3,l12,l123,l20,l21;
	inline void init(){ l1 = l20 = l3 = 0; }
	inline void Ins(int w,int c){ if (w == 1) v1[++l1] = c; else if (w == 2) v20[++l20] = c; else v3[++l3] = c; }
	inline void work(){
		register int i;
		l12 = l1 + (l20<<1),l123 = l12 + l3 * 3,l21 = l20,memcpy(v21,v20,(l20+1)<<2);
		sort(v1+1,v1+l1+1),sort(v3+1,v3+l3+1);
		for (i = 1; i < l1; i += 2) v20[++l20] = v1[i]+v1[i+1]; sort(v20+1,v20+l20+1);
		v20[0] = 0; for (i = 1; i <= l20; ++i) v20[i] += v20[i-1]; v20[l20+1] = INF; 
		for (i = 2; i < l1; i += 2) v21[++l21] = v1[i]+v1[i+1]; sort(v21+1,v21+l21+1);
		v21[0] = l1 ? v1[1] : INF; for (i = 1; i <= l21; ++i) v21[i] += v21[i-1]; v21[l21+1] = INF;
	}
	inline int ask12(int x){
		if (x <= 0) return 0; if (x > l12) return INF;
		return (x&1) ? min(v21[x>>1],v20[x+1>>1]) : (v20[x>>1]);
	}
	inline int query(int x){
		if (x <= 0) return 0; if (x > l123) return INF;
		static int i,now,ans; now = 0,ans = ask12(x);
		for (i = 1; i <= l3; ++i) now += v3[i],x -= 3,upd(ans,now+ask12(x));
		return ans;
	}
}data;
int L; struct DPv{ int f[41]; inline void init(){ for (int i = 0; i <= L; ++i) f[i] = INF; } };
inline void upd(DPv &A,DPv &B){
	static int f[41]; register int i,j;
	for (i = 0; i <= L; ++i) f[i] = INF;
	for (i = 0; i <= L; ++i) for (j = 0; i+j <= L; ++j) upd(f[i+j],A.f[i]+B.f[j]);
	memcpy(A.f,f,(L+1)<<2);
}
vector<int> G,w[M],c[M],ans0[M],ans1[M]; vector<bool>is[M];
int m,n[M],s[M],len[M],sumw[M],ans;
int k,tp[K],ax[K],ay[K],bx[K],by[K],vc[K],cnt,px[13],py[13];
DPv dp1,now,f;
inline void solve(int S){
	register int i,j; int tt,sumc = 0;
	for (i = 1; i <= cnt; ++i)
		if (S>>(i-1)&1) sumc += c[px[i]][py[i]],sumw[px[i]] += w[px[i]][py[i]],is[px[i]][py[i]] = 1; else is[px[i]][py[i]] = 0;
	for (i = 1; i <= k; ++i) if (is[ax[i]][ay[i]] && is[bx[i]][by[i]]){
		if (vc[i] >= INF){ for (i = 1; i <= cnt; ++i) if (S>>(i-1)&1) sumw[px[i]] -= w[px[i]][py[i]]; return; }
		sumc += tp[i] == 1 ? -vc[i] : vc[i];
	}
	for (now = dp1,tt = 0; tt < G.size(); ++tt){
		for (i = G[tt],f.init(),j = 0; j <= L-sumw[i]; ++j) f.f[sumw[i]+j] = ans0[i][j];
		for (j = 0; j <= sumw[i]; ++j) f.f[sumw[i]-j] = ans1[i][j];
		upd(now,f);
	}
	upd(ans,now.f[L]+sumc);
	for (i = 1; i <= cnt; ++i) if (S>>(i-1)&1) sumw[px[i]] -= w[px[i]][py[i]];
}
int main(){
	register int i,j;
	read(m),read(L),ans = INF;
	for (i = 1; i <= m; ++i){
		read(n[i]),read(s[i]),L -= s[i],w[i].resize(n[i]),c[i].resize(n[i]),is[i].resize(n[i]);
		for (j = 0; j < n[i]; ++j) read(w[i][j]),read(c[i][j]);
	}
	L = max(L,0),read(k);
	for (i = 1; i <= k; ++i){
		read(tp[i]),read(ax[i]),read(ay[i]),read(bx[i]),read(by[i]); --ay[i],--by[i],vc[i] = INF; if (tp[i] <= 2) read(vc[i]);
		if (!is[ax[i]][ay[i]]){ ++cnt; is[ax[i]][ay[i]] = 1,px[cnt] = ax[i],py[cnt] = ay[i]; }
		if (!is[bx[i]][by[i]]){ ++cnt; is[bx[i]][by[i]] = 1,px[cnt] = bx[i],py[cnt] = by[i]; }
	}
	for (dp1.init(),dp1.f[0] = 0,i = 1; i <= m; ++i){
		data.init();
		for (j = 0; j < n[i]; ++j) if (!is[i][j]) data.Ins(w[i][j],c[i][j]); else len[i] += w[i][j];
		data.work();
		if (!len[i]){ for (j = 0; j <= L; ++j) f.f[j] = data.query(s[i]+j); upd(dp1,f); continue; }
		G.push_back(i);	ans0[i].resize(L+1); for (j = 0; j <= L; ++j) ans0[i][j] = data.query(s[i]+j);
		ans1[i].resize(len[i]+1); for (ans1[i][0] = ans0[i][0],j = 1; j <= len[i]; ++j) ans1[i][j] = data.query(s[i]-j);
	}
	for (i = 0; i < 1<<cnt; ++i) solve(i);
	cout << (ans >= INF ? -1 : ans) << '\n';
	return 0;
}