（注 ：第一次打这种超出目前能力的 dp ，调了四个晚上。

简化题意：

有四位导师，他们被两两一组分成了红 / 蓝阵营，另外两两一组分成了鸭 / R 派系

有 $n$ 所**学校**，来自 $c$ 个**城市**，第 $i$ 个学校有 $s_i$ 名选手。

同一所学校的选手必须选择同一个导师。同一个城市的选手必须选择同一个阵营。同城对派系的选择没有限制。

有 $k$ 所学校的选手有自己讨厌的老师。

求一共有多少种情况，答案对 $998244353$ 取模。

(注：每个学校可以加入自己讨厌的老师的阵营/派系)

50 pts 做法：

设 dp 状态为 $f_{(0/1,i,j,k)}$，表示 dp 到第 $i$ 个学校，选择 蓝(0)/红(1) 阵营，蓝阵营有 $j$ 个人，鸭阵营有 $k$ 个人。

按城市排序后暴力枚举每个学校即可。

复杂度 $O(nM^2)$ ，可以获得 50pts 。

Code

#include<bits/stdc++.h>
#define N 35
#define M 505
using namespace std;

int read(){
	int x=0,w=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*w;
}

const int mod = 998244353;
int t,c,n,c0,c1,d0,d1,k;
int sum[N];
struct node{int s,city,hate;}sch[N];
int dp[2][N][M][M];

bool cmp(node x,node y){return x.city<y.city;}
void add(int &x,int y){x=(x+y)%mod;};

void work(){
	memset(sum,0,sizeof(sum));
	memset(sch,0,sizeof(sch));
	memset(dp,0,sizeof(dp));
	n=read();c=read();c0=read();c1=read();d0=read();d1=read();
	for(int i=1;i<=n;++i) sch[i].city=read(),sch[i].s=read(),sch[i].hate=10;
	int K=read();
	for(int i=1;i<=K;++i){
		int x=read();
		sch[x].hate=read();
	}
	sort(sch+1,sch+1+n,cmp);
	for(int i=1;i<=n;++i) sum[i]=sum[i-1]+sch[i].s;
	dp[1][0][0][0]=dp[0][0][0][0]=1;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=sum[i];++j)
			for(int k=0;k<=sum[i];++k){
				if(j>c0||sum[i]-j>c1||k>d0||sum[i]-k>d1)continue;
				if((sch[i].hate!=1)&&j>=sch[i].s)add(dp[0][i][j][k],dp[0][i-1][j-sch[i].s][k]);
				if((sch[i].hate!=0)&&j>=sch[i].s&&k>=sch[i].s)add(dp[0][i][j][k],dp[0][i-1][j-sch[i].s][k-sch[i].s]);
				if((sch[i].hate!=3))add(dp[1][i][j][k],dp[1][i-1][j][k]);
				if((sch[i].hate!=2)&&k>=sch[i].s)add(dp[1][i][j][k],dp[1][i-1][j][k-sch[i].s]);
				if(sch[i].city!=sch[i-1].city&&i!=1){
					if((sch[i].hate!=1)&&j>=sch[i].s)add(dp[0][i][j][k],dp[1][i-1][j-sch[i].s][k]);
					if((sch[i].hate!=0)&&j>=sch[i].s&&k>=sch[i].s)add(dp[0][i][j][k],dp[1][i-1][j-sch[i].s][k-sch[i].s]);
					if((sch[i].hate!=3))add(dp[1][i][j][k],dp[0][i-1][j][k]);
					if((sch[i].hate!=2)&&k>=sch[i].s)add(dp[1][i][j][k],dp[0][i-1][j][k-sch[i].s]);
				}
			}
	}
	/*
	n=1;
	for(int i=0;i<=sum[n];++i)
		for(int j=0;j<=sum[n];++j)
			if(dp[0][n][i][j])
				printf("%lld %lld %lld\n",i,j,dp[0][n][i][j]);
	*/
	int ans=0;
	for(int i=0;i<=sum[n];++i)
		for(int j=0;j<=sum[n];++j)
			add(ans,dp[0][n][i][j]),add(ans,dp[1][n][i][j]);
	printf("%d\n",ans);
}

signed main(){
	t=read();
	while(t--)work();
	return 0;
}

70 pts 做法：

考虑对阵营和派系分开背包，然后合并。

因为阵营和派系的贡献是分开的，因此只要控制人数合法，这样显然成立。

设阵营状态为 $f_{(0/1,i,j)}$，表示 dp 到第 $i$ 个学校，选择 蓝(0)/红(1) 阵营，蓝阵营有 $j$ 个人。

派系状态为 $g_{(i,j)}$ 因为派系对城市没有要求，因此少一维，其余与上述同理。

$$ans=\sum\limits_{i=sum-c1}^{c0}\sum\limits_{j=sum-d0}^{d1} \left( f_{(0,n,i)}+f_{(1,n,i)} \right)g_{(i,j)}$$

复杂度 $O(nM+M^2)$ ，结合上述方法获得 70pts 。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;

int read(){
	int x=0,w=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*w;
}

const int mod = 998244353;
int t,c,n,c0,c1,d0,d1,k;
int sum[1005];
int dp[2][35][505][505],f[2][1005][2505],g[1005][2505];
struct node{int s,city,hate;}sch[1005];

bool cmp(node x,node y){return x.city<y.city;}
void add(int &x,int y){x=(x+y)%mod;};

void solve1(){
	memset(dp,0,sizeof(dp));
	dp[1][0][0][0]=dp[0][0][0][0]=1;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=sum[i];++j)
			for(int k=0;k<=sum[i];++k){
				if(j>c0||sum[i]-j>c1||k>d0||sum[i]-k>d1)continue;
				if((sch[i].hate!=1)&&j>=sch[i].s)add(dp[0][i][j][k],dp[0][i-1][j-sch[i].s][k]);
				if((sch[i].hate!=0)&&j>=sch[i].s&&k>=sch[i].s)add(dp[0][i][j][k],dp[0][i-1][j-sch[i].s][k-sch[i].s]);
				if((sch[i].hate!=3))add(dp[1][i][j][k],dp[1][i-1][j][k]);
				if((sch[i].hate!=2)&&k>=sch[i].s)add(dp[1][i][j][k],dp[1][i-1][j][k-sch[i].s]);
				if(sch[i].city!=sch[i-1].city&&i!=1){
					if((sch[i].hate!=1)&&j>=sch[i].s)add(dp[0][i][j][k],dp[1][i-1][j-sch[i].s][k]);
					if((sch[i].hate!=0)&&j>=sch[i].s&&k>=sch[i].s)add(dp[0][i][j][k],dp[1][i-1][j-sch[i].s][k-sch[i].s]);
					if((sch[i].hate!=3))add(dp[1][i][j][k],dp[0][i-1][j][k]);
					if((sch[i].hate!=2)&&k>=sch[i].s)add(dp[1][i][j][k],dp[0][i-1][j][k-sch[i].s]);
				}
			}
	}
	int ans=0;
	for(int i=0;i<=sum[n];++i)
		for(int j=0;j<=sum[n];++j)
			add(ans,dp[0][n][i][j]),add(ans,dp[1][n][i][j]);
	printf("%lld\n",ans);
}
void solve2(){
	memset(f,0,sizeof(f));memset(g,0,sizeof(g));
	f[0][0][0]=f[1][0][0]=1;g[0][0]=1;
	for(int i=1;i<=n;++i)
		for(int j=0;j<=sum[i];++j){
			if(j>c0||sum[i]-j>c1)continue;
			if(j>=sch[i].s)add(f[0][i][j],f[0][i-1][j-sch[i].s]);
			add(f[1][i][j],f[1][i-1][j]);
			if(sch[i].city!=sch[i-1].city&&i!=1){
				if(j>=sch[i].s)add(f[0][i][j],f[1][i-1][j-sch[i].s]);
				add(f[1][i][j],f[0][i-1][j]);
			}
		}
	for(int i=1;i<=n;++i)
		for(int j=0;j<=sum[i];++j){
			if(j>d0||sum[i]-j>d1)continue;
			add(g[i][j],g[i-1][j]);
			if(j>=sch[i].s)add(g[i][j],g[i-1][j-sch[i].s]);
		}
	int ans=0;
	for(int i=sum[n]-c1;i<=c0;++i)
		for(int j=sum[n]-d1;j<=d0;++j)
			add(ans,g[n][j]*(f[0][n][i]+f[1][n][i]));
	printf("%lld\n",ans);
}

signed main(){
	t=read();
	while(t--){
		n=read();c=read();c0=read();c1=read();d0=read();d1=read();
		for(int i=1;i<=n;++i) sch[i].city=read(),sch[i].s=read(),sch[i].hate=10;
		int K=read();
		for(int i=1;i<=K;++i){
			int x=read();
			sch[x].hate=read();
		}
		sort(sch+1,sch+1+n,cmp);
		for(int i=1;i<=n;++i) sum[i]=sum[i-1]+sch[i].s;
		if(n<=30) solve1();
		else if(k==0) solve2(); 
	}
	return 0;
}

100 pts 做法：

(因为我的 70 pts 做法比较劣，所以到正解跳度有点大。

首先我们发现，例如 50 pts 做法里的大数组一次 dp 显然无法优化，正确做法应当是形如 70 pts 的背包合并。

那么现在考虑带有特殊限制的学校，一个很自然的想法就是将他们与无限制的学校分开处理。

紧接着我们又发现，这时对于两者的合并非常困难，很大的原因是因为特殊性质学校的选择会对于同城市其他学校的选择产生影响，我们在合并时考虑这些情况会导致复杂度和 dp 维度的上升。

那么不妨转化一下思路，由于特殊性质学校会影响其所处的城市，那么我们考虑将这个性质打到城市上，也就是对于阵营的处理已城市为单位进行。

设 $F_{(i,j,k,0/1)}$ 是对于前 $i$ 所有限制的城市，有 $j$ 名选手加入蓝阵营，有 $k$ 名选手加入鸭阵营，以及此城市加入的是蓝(0)/红(1)阵营。

即可对于 $F$ 数组进行形如 50 pts 做法的转移，复杂度 $O(ksM^2)$ 。

空间 $O(ksM^2)$ 爆了怎么办，滚动数组啊。(说实话滚了之后好写很多。

接下来考虑合并整体答案。

对于每个 F ，用 f 去匹配阵营的城市，用 g 去匹配派系的学校。

相较于对这些城市中的每所学校进行处理的 $O(ksM^2)$ ，这样显然快些。

前缀和优化计算即可。

复杂度 $O(nM+kM^2)$ 卡卡常可以得到 100 pts 。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;

int read(){
    int x=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*w;
}

const int mod = 998244353;
int t,c,n,c0,c1,d0,d1,k,tot,len1,len2;
int sum[1005];
int F[2][2][2505][2505],f[2505],g[2505],f_sum[2505],g_sum[2505],city_sum[2505];
bool city[2505],use[2505];
struct node{int s,c,city,hate;}sch[1005],sch1[1005],sch2[1005];

bool cmp(node x,node y){return x.city<y.city;}
void add(int &x,int y){x=(x+y)%mod;};

void work(){
    memset(city,0,sizeof(city));memset(use,0,sizeof(use));
    tot=len1=len2=0;
    n=read();c=read();c0=read();c1=read();d0=read();d1=read();
    for(int i=1;i<=c;++i) city_sum[i]=0;
    for(int i=1;i<=n;++i) sch[i].city=read(),sch[i].s=read(),tot+=sch[i].s,sch[i].hate=10,city_sum[sch[i].city]+=sch[i].s;
    int K=read();
    for(int i=1;i<=K;++i){int x=read();sch[x].hate=read();city[sch[x].city]=1;}
    for(int i=1;i<=n;++i){
        if(sch[i].hate<10) sch1[++len1]=sch[i];
        else sch2[++len2]=sch[i];
    }
    sort(sch1+1,sch1+1+len1,cmp);
    for(int i=1;i<=len1;++i){
        if(!use[sch1[i].city])
            sch1[i].c=city_sum[sch1[i].city],use[sch1[i].city]=1;
        //每个城市的人数只计算一次。
    };

	memset(F,0,sizeof(F));
	F[0][0][0][0]=1;
	int res=0,last=0;
	for(int i=1;i<=len1;++i){
		last=res,res+=sch1[i].s;//便于优化
		int now=i&1;
		for(int t=0;t<=1;++t)
			for(int x=0;x<=c0;++x)
				for(int y=0;y<=res;++y)
					F[t][now][x][y]=0;
		for(int j=0;j<=c0;++j)
			for(int k=0;k<=res;++k){
				if(sch1[i].hate!=1&&j>=sch1[i].c)add(F[0][now][j][k],F[0][now^1][j-sch1[i].c][k]);
				if(sch1[i].hate!=0&&j>=sch1[i].c&&k>=sch1[i].s)add(F[0][now][j][k],F[0][now^1][j-sch1[i].c][k-sch1[i].s]);
				if(sch1[i].hate!=3)add(F[1][now][j][k],F[1][now^1][j][k]);
				if(sch1[i].hate!=2&&k>=sch1[i].s)add(F[1][now][j][k],F[1][now^1][j][k-sch1[i].s]);
				if(sch1[i].city!=sch1[i-1].city||i==1){
					if(sch1[i].hate!=1&&j>=sch1[i].c)add(F[0][now][j][k],F[1][now^1][j-sch1[i].c][k]);
					if(sch1[i].hate!=0&&j>=sch1[i].c&&k>=sch1[i].s)add(F[0][now][j][k],F[1][now^1][j-sch1[i].c][k-sch1[i].s]);
					if(sch1[i].hate!=3)add(F[1][now][j][k],F[0][now^1][j][k]);
					if(sch1[i].hate!=2&&k>=sch1[i].s)add(F[1][now][j][k],F[0][now^1][j][k-sch1[i].s]);
				}
			}
	}

	memset(f,0,sizeof(f));memset(g,0,sizeof(g));
	f[0]=g[0]=f_sum[0]=g_sum[0]=1;
	for(int i=1;i<=c;++i){
		if(city[i]||city_sum[i]==0) continue;
			for(int j=c0;j>=city_sum[i];--j)
				add(f[j],f[j-city_sum[i]]);
	}
	for(int i=1;i<=c0;++i)f_sum[i]=(f_sum[i-1]+f[i])%mod;
	for(int i=1;i<=len2;++i)
		for(int j=d0;j>=sch2[i].s;--j)
			add(g[j],g[j-sch2[i].s]);
	for(int i=1;i<=d0;++i)g_sum[i]=(g_sum[i-1]+g[i])%mod;
	int ans=0;
	for(int t=0;t<=1;++t)for(int i=0;i<=c0;++i)for(int j=0;j<=d0;++j){
			if(!F[t][len1&1][i][j]) continue;
			int t1=c0-i,t2=max(0ll,tot-d1-j),t3=max(0ll,tot-c1-i),t4=d0-j;
			if(t3>t1||t2>t4)continue;
			add(ans,F[t][len1&1][i][j]*(f_sum[t1]-f_sum[t3-1]+mod)%mod*(g_sum[t4]-g_sum[t2-1]+mod)%mod);
		}
	printf("%lld\n",ans);
	/*
	for(int i=0;i<=1;++i){
    	for(int j=0;j<=c0;++j){
    		for(int k=0;k<=d0;++k)
    			printf("%lld ",F[i][len1&1][j][k]);
    		puts("");
    	}
    }
    */

}

signed main(){

	t=read();
	while(t--)work();
	return 0;
}

后话

此题考察了背包的极致应用，也让作者知道了自己对于此类 dp 的理解不足。

dp 的转移要巨大严谨，对 dp 状态要巨大清晰。

这辈子都不想打这种东西了。

另外：这辈子没想过背包这么毒瘤。