Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:见内In Reply To:见内 Posted by:madongfly at 2007-07-31 19:38:17 > 将n个请求分成2n个事件,一种请求厅房,一种释放厅房,按发生时间排序,时间相同的请求事件在前。 > dp[i][j]表示第i个事件发生使得使用厅房的状态为j 可不可能。 > j的二进制形式表示各厅房的使用状态。 > > 剩下的状态转移就比较好想了吧。 > #include <iostream> #include <string.h> #include <utility> #include <math.h> #include <stdlib.h> #include <stdio.h> #include <queue> #include <vector> #include <set> using namespace std; int t; struct Event{ bool hired; int t,i; } e[24]; bool operator<(const Event &e1, const Event& e2){ if(e1.t==e2.t){ return e1.hired; } return e1.t<e2.t; } vector<int> hall[12]; int dp[24][1<<8]; int main(){ scanf("%d",&t); int R; while(t--){ scanf("%d",&R); int a,b,cnt,tmp; for(int i=0;i<R;i++){ hall[i].clear(); scanf("%d%d",&a,&b); scanf("%d",&cnt); e[2*i].t = a; e[2*i].hired = true; e[2*i].i = i; e[2*i+1].t = b; e[2*i+1].hired = false; e[2*i+1].i = i; for(int j=0;j<cnt;j++){ scanf("%d",&tmp); hall[i].push_back(tmp-1); } } memset(dp,0,sizeof dp); sort(e,e+2*R); for(int i=0;i<hall[e[0].i].size();i++) dp[0][1<<hall[e[0].i][i]] = 1; int x; for(int i=0;i<2*R-1;i++) for(int j=0;j<(1<<8);j++){ if(!dp[i][j]) continue; x = e[i+1].i; for(int k=0;k<hall[x].size();k++){ int y = 1<<hall[x][k]; if(e[i+1].hired){ if((j^y) > j) dp[i+1][j^y]=1; }else{ if((j^y)<j) dp[i+1][j^y]=1; } } } if(dp[2*R-1][0]) printf("YES\n"); else printf("NO\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator