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

AC 50留贴 ,WA的注意了!

Posted by windyrobin at 2008-08-06 13:27:43 on Problem 2184
//2184 Accepted 208K 766MS C++ 1463B 
//此题用dp做简直是噩梦!!此处用回溯加剪枝 ,WA 、TLE 各 N次 (N>10) 后
//终于AC!!湿了...
//预处理阶段 ,即使f+s<0 ,此数据也有可能被加入 !!!
//比如 先前 sum为 8 -2  ,当前为-3 ,2 ,加入后就满足条件,变为5 ,0
//另外剪枝的约束要千万注意
回溯代码:(好像有规定 ,不能贴全部,呵呵)
void backTrack(int n ,int sumS ,int sumF)
{

	if(sumF+sumS > sumT && sumS>=0 && sumF>=0 )
		sumT=sumF+sumS;
	if(n==0)
		return ;
	if(sumS+dataSum[n].s<0 || sumF+dataSum[n].f<0)
		return ;
	if(sumS+sumF+dataLog[n] <= sumT )
		return ;
	
	backTrack(n-1 ,sumS+data[n].s ,sumF+data[n].f);
	backTrack(n-1 ,sumS ,sumF);
}

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