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 frankvista at 2010-11-06 22:42:16 on Problem 1185
const
	SIZE_DP = 1 shl 21;
	MAXN = 120; MAXM = 20;

var
	dp,_dp : array[0..SIZE_DP] of longint;
	ch : char;
	sta : array[1..MAXN,1..MAXM] of longint;
	list,_list : array[1..SIZE_DP] of longint;
	ans,pline,i,j,n,m,len,_len : longint;
	_state,SIZEUP : longint;

function max(x,y : longint) : longint;
begin
	if x > y then exit(x) else exit(y);
end;

procedure treat(state,now,num : longint);
begin
	if now >= m then begin
		if _dp[state] = -1 then begin
			inc(_len); _list[_len] := state; _dp[state] := dp[_state]+num;
		end
		else _dp[state] := max(_dp[state],dp[_state]+num);		
		exit;
	end;
	while (state shr (now+now)) and 3 > 0 do begin
		if (state shr (now+now)) and 3 = 1 then state := state and not (3 shl (now+now)) else state := state and not (1 shl (now+now+1));
		inc(now); 
		if now >= m then begin
			if _dp[state] = -1 then begin
				inc(_len); _list[_len] := state; _dp[state] := dp[_state]+num;
			end
			else _dp[state] := max(_dp[state],dp[_state]+num);	
			exit;
		end;
	end;
	treat(state,now+1,num);
	if sta[pline][now+1] = 0 then exit;
	state := state or (3 shl (now+now)); inc(num);
	inc(now); 
	if now >= m then begin
		if _dp[state] = -1 then begin
			inc(_len); _list[_len] := state; _dp[state] := dp[_state]+num;
		end
		else _dp[state] := max(_dp[state],dp[_state]+num);		
		exit;
	end;
	if (state shr (now+now)) and 3 = 3 then state := state and not (1 shl (now+now+1)) else state := state and not (3 shl (now+now)); 
	inc(now); 
	if now >= m then begin
		if _dp[state] = -1 then begin
			inc(_len); _list[_len] := state; _dp[state] := dp[_state]+num;
		end
		else _dp[state] := max(_dp[state],dp[_state]+num);		
		exit;
	end;
	if (state shr (now+now)) and 3 = 3 then state := state and not (1 shl (now+now+1)) else state := state and not (3 shl (now+now)); 
	treat(state,now+1,num);
end;

begin
	readln(n,m);
	for i := 1 to n do begin
		for j := 1 to m do begin
			read(ch);
			if ch = 'P' then sta[i,j] := 1 else sta[i,j] := 0;
		end;
		readln;
	end;
	SIZEUP := 1 shl (m+m)-1;
	filldword(dp,SIZEUP,-1); list[1] := 0; len := 1; dp[0] := 0;
	for pline := 1 to n do begin
		filldword(_dp,SIZEUP,-1); _len := 0;
		for j := 1 to len do begin
			_state := list[j]; treat(list[j],0,0);
		end;
		dp := _dp; len := _len; list := _list;
	end;
	ans := 0;
	for i := 1 to len do if dp[list[i]] > ans then ans := dp[list[i]];
	writeln(ans);
end.

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