作者SHBK (头脑好钝 唉)
看板ACMCLUB
标题Re: [问题] 861
时间Wed Aug 31 17:45:26 2005
※ 引述《kc655039 (NNN  )》之铭言：
: ※ 引述《SHBK (头脑好钝 唉)》之铭言：
: : 这一题用backtracking 会很慢..即使有bounded条件也没快多少
: : 这题要用DP去做 会超快...
: : http://www.csie.nctu.edu.tw/~chchu/phpBB/viewtopic.php?t=354
: 我知道可以用推的,我861用backtracking是000080的时间,
: 你的方法跟我用的差不多一模一样呢.....(之前有人把棋盘转四十五度角,
: 分两种颜色分别补格子补成长方形也解开了).
: 可是我刚刚用推的解开10237也才....000088...,
: 应该算是DP吧....连DP都比正常人慢到底怎麽回事?????
: 还有就是.....用那个DP的程式跑861其实是000064..
10237 我还没解
861我跑的时间是0.014
我想你的演算法没有问题
要快的话 就要用C写(cin 改成 scanf 这里会快不少)
还有你有function call呼叫当然会比较慢罗(我是都写在main里)
每次输入就把最大的n存起来(max) 下一次n<max 直接查表就好
所以用两个array存两种颜色的组合数(有初始化)
大概降子就会快很多了
: 也许这些数字没什麽意义吧,但是ghost 77的就显然写的比较好^^
: 请教一下你们写这题的时候有做这种事情吗:long long result[N][M]={0};
: 就是把存放最後结果的array初始化.
: 还有就是大家开了一些什麽array?
: 真的满想了解到底慢在哪边,因为其实我都想过要省下时间,
: 但成绩出来就是不好看...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.140.79.125