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 |
事实证明...16MS和0MS 的差距在一个FILLCHAR之间16MS版: b:array[0..11111] of longint; bbb:array[1..2222] of boolean; fillchar(bbb,sizeof(b),false); //注意..sizeof打错了... 0MS版: b:array[0..11111] of longint; bbb:array[1..11111] of boolean; fillchar(bbb,sizeof(b),false); //注意..0MS的数组开的大小比16MS的大.. 虽然清空数组更多了...但是很多神奇的原因综合起来导致...数组大的反而快 结论:用LONGINT数组清空BOOL数组...大小越接近LONGINT数组,清空速度越快... 当然SIZEOF改正后都是0MS ...好吧..算法什么的.... 穷举长度,检验可不可以 注意穷举时是穷举原始木棍根数..(这样比直接穷举长度,快一点) (设SUM为全部木棍长度和,MAX为数据中木棍最长的那一根) 从 SUM div MAX 穷举到 1 就行了.... 优化的话: HASH加剪枝..优化后各种猥琐数据都1S内无问题.. HASH比较多比较烦 ... f[i] 表示 长为I的木棍数目 b[i] 表示 去重后 第I长的木棍的长度 b[st[i]] 表示 某个原始木棍还有 I 长度要填充时 , 能填的最长木棍长度 (如果单解释ST会表达不清...这样解释应该没问题) 然后 2个剪枝 1. 搜索填充每一个原始木棍时,后一根不长于前一个.... (- -填充是组合嘛...顺序就无所谓了) 2. 对于每根原始木棍填入的第一个木棍,只填入当前最长的,不穷举其他的 (理由和上面一样...反正都要填..早填晚填都一样) ...因为没删掉调试输出语句..WA了无数次...唉...悲剧....要是NOIP就出事了... Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator