随笔-72  评论-126  文章-0  trackbacks-0
http://acm.hdu.edu.cn/showproblem.php?pid=1565
唉。效率很低很低,跑了4000MS,是最暴力的过法
不过思路很简单
先是dfs出一行内不相邻的所有情况
用二进制记录下所有的状态,存在ku数组里
然后就开始DP
i是代表行数
j和l是代表状态的下标
j是这一行的,l是上一行的
ku[j]是代表状态
当(ku[j]
&ku[l])==0的时候就开始dp
这个是状态转移方程
dp[i][j] 
= Max(dp[i][j],dp[i-1][l] + add(i,ku[j]));

然后就是取出最大值。。。输出


唉,跑的都快超时了,看看别人0MS过的真是惭愧阿
还有一道50*50的,用这样的暴力一定过不了,以后要想出更好的办法
posted on 2009-02-19 14:57 shǎ崽 阅读(708) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理