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

Re:这题算是NOI2005智慧珠游戏的简化版吗?

Posted by JiaJunpeng at 2014-03-24 11:34:27 on Problem 2755 and last updated at 2014-03-24 11:37:45
In Reply To:Re:这题算是NOI2005智慧珠游戏的简化版吗? Posted by:JiaJunpeng at 2014-03-23 00:31:52
> 
> 这道题 不限制 Domino 个 数的话状压dp比较靠谱,行dp一次,列dp一次 
> 限制 一行 格子<=6,状态数 应该比较少,  但是 题目要求 domino只能用一次,
> 就要*2^12状态,比直接搜状态空间 少点,但是还是不靠谱

又YY了一下,可以 先不考虑domino个数,直接dp(复杂度 2^12*60*12),然后暴搜,
dp值为0的时候剪枝(差不多相当于利用dp值作为股价函数),这个做法应该比较快吧。
复杂度应该是 O(ans'),ans'为不考虑domino个数的结果。。不过代码量。。。。哎。。。。。。。

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