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怎么办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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator