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

• 北大的服务器就是好，200000*100的dp才用了94ms，不知道区域赛的测试系统性能怎么样 (598) B06350214 2008-08-29 16:41:58
  • 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
• Re:AC 50留贴 ，WA的注意了！ (23) windows8 2011-05-03 14:49:38