Luogu5289 十二省联考2019皮配（动态规划）

时间：2023-03-09 09:13:29
Luogu5289 十二省联考2019皮配（动态规划）

　　将选择导师看成先选阵营再选派系，这样有显然的O(nm2)暴力，即按城市排序后，设f[i][j][k]为前i个学校中第一个阵营有j人第一个派系有k人的方案数，暴力背包。

　　对于k=0，可以发现选阵营和选派系是两个独立的过程。于是O(nm)暴力背包再将方案数相乘即可。

　　考虑原题，注意到如果一个城市不包含有限制的学校，可以直接使用k=0的方法；对于同城市存在有限制学校而自身没有限制的，其选择派系的过程与限制无关，可以将这部分背包，而选择阵营的过程则和有限制学校放在一起用最开始的暴力完成，这里同一城市的无限制学校可以合并起来。于是复杂度O(nm+km2)。稍微卡一下可以做到复杂度O(nm+kmΣsk)，其中Σsk为有限制学校总人数。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 1010

#define M 2510

#define P 998244353

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int T,n,c,k,C0,C1,D0,D1,S,dslk[N],id[N],f[M],g[M],h[M][M],h2[M][M];

bool islim[N];

struct data

{

	int x,y,i;

	bool operator <(const data&a) const

	{

		return x<a.x;

	}

}a[N];

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

	const char LL[]="%I64d\n";

#else

	const char LL[]="%lld\n";

#endif

	T=read();

	while (T--)

	{

		n=read(),c=read();

		C0=read(),C1=read(),D0=read(),D1=read();S=0;

		for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].i=i,S+=a[i].y;

		sort(a+1,a+n+1);

		for (int i=1;i<=n;i++) id[a[i].i]=i;

		C1=max(0,S-C1),D1=max(0,S-D1);

		k=read();

		memset(dslk,0,sizeof(dslk));

		memset(islim,0,sizeof(islim));

		for (int i=1;i<=k;i++)

		{

			int x=id[read()],y=read();

			dslk[x]=y+1;islim[a[x].x]=1;

		}

		memset(f,0,sizeof(f));memset(g,0,sizeof(g));memset(h,0,sizeof(h));

		f[0]=g[0]=1;h[0][0]=1;

		int tot=0,tot2=0;

		for (int i=1;i<=n;i++)

		{

			int t=i;

			while (t<n&&a[t+1].x==a[i].x) t++;

			int s=0;

			for (int j=i;j<=t;j++)

			if (!dslk[j])

			{

				s+=a[j].y;

				for (int k=D0;k>=a[j].y;k--) inc(g[k],g[k-a[j].y]);

			}

			if (islim[a[i].x])

			{

				for (int j=i;j<=t;j++)

				{

					tot+=a[j].y;

					if (dslk[j]) tot2+=a[j].y;

				}

				for (int x=0;x<=min(tot,C0);x++)

					for (int y=0;y<=min(tot2,D0);y++)

					h2[x][y]=x>=s?h[x-s][y]:0;

				for (int j=i;j<=t;j++)

				if (dslk[j])

				{

					for (int x=min(tot,C0);x>=0;x--)

						for (int y=min(tot2,D0);y>=0;y--)

						{

							h2[x][y]=0;

							if (dslk[j]!=1&&x>=a[j].y&&y>=a[j].y) inc(h2[x][y],h2[x-a[j].y][y-a[j].y]);

							if (dslk[j]!=2&&x>=a[j].y) inc(h2[x][y],h2[x-a[j].y][y]);

						}

				}

				for (int j=i;j<=t;j++)

				if (dslk[j])

				{

					for (int x=min(tot,C0);x>=0;x--)

						for (int y=min(tot2,D0);y>=0;y--)

						{

							if (dslk[j]==4) h[x][y]=0;

							if (dslk[j]!=3&&y>=a[j].y) inc(h[x][y],h[x][y-a[j].y]);

						}

				}

				for (int x=0;x<=min(tot,C0);x++)

					for (int y=0;y<=min(tot2,D0);y++)

					inc(h[x][y],h2[x][y]);

			}

			else for (int k=C0;k>=s;k--) inc(f[k],f[k-s]);

			i=t;

		}

		for (int i=1;i<=C0;i++) inc(f[i],f[i-1]);

		for (int i=1;i<=D0;i++) inc(g[i],g[i-1]);

		int ans=0;

		for (int i=0;i<=C0;i++)

			for (int j=0;j<=D0;j++)

			inc(ans,1ll*(f[C0-i]-f[max(C1-i,0)-1]+P)*(g[D0-j]-g[max(D1-j,0)-1]+P)%P*h[i][j]%P);

		cout<<ans<<endl;

	}

	return 0;

}

　　

相关文章