大朗网站建设培训,淘宝客cms网站建设,扬州百度推广公司,南京seo外包正题 题目大意 nnn个人排队#xff0c;mmm个条件(u,v)(u,v)(u,v)表示uuu要排在vvv前#xff0c;可以去掉kkk个#xff0c;求方案总数 解题思路
考虑依次插入人在队头 对于状态1表示已经在队列里#xff0c;0表示不在 fi,jf_{i,j}fi,j表示iii表示状态,jjj表示违背了的条件…正题 题目大意
nnn个人排队mmm个条件(u,v)(u,v)(u,v)表示uuu要排在vvv前可以去掉kkk个求方案总数 解题思路
考虑依次插入人在队头 对于状态1表示已经在队列里0表示不在 fi,jf_{i,j}fi,j表示iii表示状态,jjj表示违背了的条件个数。 然后枚举队头的是哪个人计算出插入他前的状态lastlastlast和将他插入队头会违背的条件个数noknoknok。
动态转移fi,jflast,j−nokf_{i,j}f_{last,j-nok}fi,jflast,j−nok codecodecode
#includecstdio
#define N 21
using namespace std;
const int XJQ1e97;
int n,m,k,atk[N],f[1N][N],ans,MS;
int count_one(int x){int ans0;while(x){x-(x-x);ans;}return ans;
}
int main()
{freopen(count.in,r,stdin);freopen(count.out,w,stdout);scanf(%d%d%d,n,m,k);for(int i1;im;i){int x,y;scanf(%d%d,x,y);atk[y-1]|(1(x-1));}MS1n;f[0][0]1;for(int i0;iMS;i)for(int j0;jn;j)if((ij)1){int lasti^(1j);int nokcount_one(atk[j]last);for(int qnok;qk;q)(f[i][q]f[last][q-nok])%XJQ;}for(int i0;ik;i)ans(ansf[MS-1][i])%XJQ;printf(%d,ans);
}
