题解：P1386 座位安排

思路

依题 dp。

组合数学前面题解的 dl 已讲得清晰了，在这里不过多赘述。乘法原理。小学知识。

奉天承运,皇帝诏曰：

钦定

hzh

数组，

hzh_i=后面“预定座位”的人数

。故坐不下时，即当

hzh_i > n-i+1

时，应当~~挤挤凑合着坐~~判无解。

钦定

C

矩阵，

C_j^i

表示从

\max(j,i)

个数中选

\min(j,i)

个数的方法和。易转移如下：

C_j^i=(C^{i-1}_{j-1}+C^{i-1}_j)

。

钦定

dp

矩阵，

dp_j^i

表示在编号大于等于

i

的人中确定

j

人之座位的方法总和数。易转移如下：

dp_j^i=\sum_{k=0}^j dp_{j-k}^{i-1}\times C_k^j

。

敬告众卿：勿忘取 %。

码：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
void dui(int x)
{
	cout<<"YES"<<" "<<x<<endl;
}
void cuo()
{
	cout<<"NO"<<endl;
}
int hzh[305],c[305][305],dp[305][305];
signed main()
{
	int  t;
	cin>>t;
	while(t--)
	{
		int n,m,mod;
		cin>>n>>m>>mod;
		bool flag=0;
		memset(hzh,0,sizeof(hzh));
		memset(dp,0,sizeof(dp));
		for(int i=0;i<=300;i++)
		{
			c[i][0]=c[i][i]=1;
			for(int j=1;j<=i;j++)	c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
			
		}
		for(int i=1;i<=m;i++)
		{
			int x;
			cin>>x;
			int y;
			cin>>y;
			hzh[y]++;
		}
		for(int i=n;i>=1;i--)	hzh[i]+=hzh[i+1];
		for(int i=1;i<=n;i++)
		{
			if(hzh[i]>n-i+1)
			{
				cuo();
				flag=1;
				break;
			}
		}
		if(flag==1)	continue;
		for(int i=0;i<=n;i++)
		{
			if(i)	dp[n+1][i]=0;
			else	dp[n+1][i]=1;
		}
		for(int i=n;i>=1;i--)
		{
			for(int j=0;j<=n-i+1-hzh[i]&&j>=0;j++)
			{
				for(int k=0;k<=j;k++) 
				{
					dp[i][j]=(dp[i][j]+c[j][k]*dp[i+1][j-k])%mod;
				}
			}
		}
		dui(dp[1][n-m]);
	}
}

题解：P1386 座位安排

文章操作

思路

码：

相关推荐

评论

题解：P1386 座位安排