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ǎ崽 阅读(716)
评论(0) 编辑 收藏 引用