【bzoj2302】【HNOI2011】【problem c】

2302: [HAOI2011]Problem c

http://www.lydsy.com/JudgeOnline/problem.php?id=2302
Time Limit: 30 Sec Memory Limit: 256 MB
Submit: 317 Solved: 167
[Submit][Status][Discuss]
Description

给n个人安排坐位，先给每一个人1个1~n的编号，设第i个人的编号为ai（不同人的编号可以相同），接着从第1个人开始，大家顺次入坐，第i个人来了以后尝试坐到ai，如果ai被占据了，就尝试ai+1，ai+1也被占据了的话就尝试ai+2，……，如果1直尝试到第n个都不行，该安排方案就不合法。但是有m个人的编号已肯定(他们也许贿赂了你的上司…)，你只能安排剩下的人的编号，求有多少种合法的安排方案。由于答案可能很大，只需输出其除以M后的余数便可。

Input

第1行1个整数T，表示数据组数

对每组数据，第1行有3个整数，分别表示n、m、M

若m不为0，则接下来1行有m对整数，p1、q1，p2、q2 ,…, pm、qm，其中第i对整数pi、qi表示第pi个人的编号必须为qi

Output

对每组数据输出1行，若是有解则输出YES，后跟1个整数表示方案数mod M，注意，YES和数之间只有1个空格，否则输出NO

Sample Input

4 3 10

1 2 2 1 3 1

10 3 8882

7 9 2 9 5 10

Sample Output

YES 4

思路：这是1道比较好的dp。
我们可以先斟酌1下无解的情况：
我们用s[i]数组，表示编号大于等于i的编号的个数。这样明显就能够得出当s[i]>n-i+1时这个序列就是不合法的，反之，就为合法的。
根据上面的分析，我们可以知道序列是不是合法只跟s有关。
然后我们再来斟酌没有限制的合法的情况：
f[i][j]表示元素值大于等于i，有j个元素已肯定了（j<=n-i+1）
那末dp方程为：

f[i][j]=∑k=0j(f[i+1][j?k]?c[j][k])

c[j][k]表示j个元素当选k个位置放i的组合数。
再斟酌有限制的情况：
其实有限制的情况也很简单，只需要把j的限制改成j<=n-i+1-s[i]就行了，s[i]就是之前求的编号大于等于i的个数。

/**************************************************************

    Problem: 2302

    User: _vampire_

    Language: C++

    Result: Accepted

    Time:5460 ms

    Memory:2776 kb

****************************************************************/

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int t,n,m,M,use[310]; long long s[310],f[310][310],c[310][310]; bool ff=true; int main() { scanf("%d",&t); while(t--){ memset(use,0,sizeof(use)); memset(s,0,sizeof(s)); memset(f,0,sizeof(f)); memset(c,0,sizeof(c)); int i,j,x,y,k; ff=true; scanf("%d%d%d",&n,&m,&M); for(i=1;i<=m;++i){ scanf("%d%d",&x,&y); use[y]+=1; } for(i=n;i>=1;--i){ s[i]=s[i+1]+use[i]; if(s[i]>n-i+1){ ff=false; printf("NO "); } } if(!ff) continue; for(i=0;i<=n;++i){ c[i][0]=c[i][i]=1; for(j=1;j<i;++j) c[i][j]=(c[i⑴][j⑴]+c[i⑴][j])%M; } f[n+1][0]=1; for(i=1;i<=n;++i) f[n+1][i]=0; for(i=n;i>=1;--i){ for(j=0;j<=n-s[i]-i+1;++j){ for(k=0;k<=j;++k){ f[i][j]=(f[i][j]+f[i+1][j-k]*c[j][k])%M; } } } printf("YES %d ",f[1][n-m]); } }

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！

波比源码 » 【bzoj2302】【HNOI2011】【problem c】

分享到：