| ||||||||||
| 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 | |||||||||
TLE了,哪位仁兄帮帮我看一下:#include <iostream>
#include <fstream>
using namespace std;
int reqnum; //请求的次数
struct timetable{int start,end;} time[2001];
int candihall[2001][10];///candihall[i][j]代表第i个请求的各个备选hall
int candihnum[2001];/// 代表第i个请求有多少个备选hall
int timemark[10][10001];///标记可用的时间线段 timemark[1][1]代表第1个hall在时刻1是否可用
bool compute(int p){
if(p==reqnum){
return true;
}
for(int i=0;i<candihnum[p];i++){
bool test=true;
for(int tm=time[p].start;tm<=time[p].end&&test;tm++){
if(timemark[candihall[p][i]][tm]==1)test=false; //该时间段不可用
}
if(test){
for(tm=time[p].start;tm<=time[p].end;tm++)
timemark[candihall[p][i]][tm]=1;
bool testp=compute(p+1);
if(testp)return true;
for(tm=time[p].start;tm<=time[p].end;tm++)
timemark[candihall[p][i]][tm]=0;
}
}
return false;
}
void init(){
memset(candihall,0,sizeof(candihall));
memset(candihnum,0,sizeof(candihnum));
memset(timemark,0,sizeof(timemark));
}
void main(){
// ifstream cin("data.txt");
int testcase;
cin>>testcase;
for(int i=0;i<testcase;i++){
cin>>reqnum;
init();
for(int j=0;j<reqnum;j++){
cin>>time[j].start>>time[j].end;
cin>>candihnum[j];
for(int k=0;k<candihnum[j];k++)
cin>>candihall[j][k];
}
bool test=compute(0);
if(test)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator