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被占據(jù)了，就嘗試ai+1，ai+1也被占據(jù)了的話就嘗試ai+2，……，如果1直嘗試到第n個都不行，該安排方案就不合法。但是有m個人的編號已肯定(他們也許賄賂了你的上司…)，你只能安排剩下的人的編號，求有多少種合法的安排方案。由于答案可能很大，只需輸出其除以M后的余數(shù)便可。
Input
第1行1個整數(shù)T，表示數(shù)據(jù)組數(shù)
對每組數(shù)據(jù)，第1行有3個整數(shù)，分別表示n、m、M
若m不為0，則接下來1行有m對整數(shù)，p1、q1，p2、q2 ,…, pm、qm，其中第i對整數(shù)pi、qi表示第pi個人的編號必須為qi
Output
對每組數(shù)據(jù)輸出1行，若是有解則輸出YES，后跟1個整數(shù)表示方案數(shù)mod M，注意，YES和數(shù)之間只有1個空格，否則輸出NO
Sample Input
2
4 3 10
1 2 2 1 3 1
10 3 8882
7 9 2 9 5 10
Sample Output
YES 4
NO
思路：這是1道比較好的dp。
我們可以先斟酌1下無解的情況：
我們用s[i]數(shù)組，表示編號大于等于i的編號的個數(shù)。這樣明顯就能夠得出當s[i]>n-i+1時這個序列就是不合法的，反之，就為合法的。
根據(jù)上面的分析，我們可以知道序列是不是合法只跟s有關(guān)。
然后我們再來斟酌沒有限制的合法的情況：
f[i][j]表示元素值大于等于i，有j個元素已肯定了（j<=n-i+1）
那末dp方程為：
/**************************************************************
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]);
}
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學習，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
