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ǎ崽 閱讀(719)
評論(0) 編輯 收藏 引用