> //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);
> }

• Re:北大的服务器就是好，200000*100的dp才用了94ms，不知道区域赛的测试系统性能怎么样 (34) snlia 2011-12-17 09:00:33
• Re:北大的服务器就是好，200000*100的dp才用了94ms，不知道区域赛的测试系统性能怎么样 (6) stephenzeng 2019-07-18 19:39:37