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

事实证明...16MS和0MS 的差距在一个FILLCHAR之间

Posted by wilyin at 2010-12-21 21:07:23 on Problem 1011
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:
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