Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

TLE了,哪位仁兄帮帮我看一下:

Posted by zhb_msqx at 2007-08-21 20:21:05 on Problem 3303
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator