Detail of message

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

Re:原来我不是唯一一个在J上脑抽写状压DP的...

Posted by moonancient at 2009-11-10 12:33:32
In Reply To:Re:原来我不是唯一一个在J上脑抽写状压DP的... Posted by:huicpc035 at 2009-11-10 09:07:24

事后想过，当时做的一大堆优化里面关键性的只有两个：
1、记录合法状态集，只在这个集合上DP，比如需要两个DC的阵型，所有第一个DC没人而第二个DC有人的就都是非法状态
2、状态记录用一维数组f[1<<11]，这样比用二维数组f[n][1<<11]大大降低了内存访问开销，因为只需要8kb的空间，可以完全在L1缓存上完成

Followed by:

Post your reply here:

Home Page Go Back To top