http://acm.hdu.edu.cn/showproblem.php?pid=1565唉。效率很低很低，跑了4000MS，是最暴力的過法
不過思路很簡單
先是dfs出一行內(nèi)不相鄰的所有情況
用二進(jìn)制記錄下所有的狀態(tài)，存在ku數(shù)組里
然后就開始DP
i是代表行數(shù)
j和l是代表狀態(tài)的下標(biāo)
j是這一行的，l是上一行的
ku[j]是代表狀態(tài)
當(dāng)(ku[j]&ku[l])==0的時(shí)候就開始dp
這個(gè)是狀態(tài)轉(zhuǎn)移方程
dp[i][j] = Max(dp[i][j],dp[i-1][l] + add(i,ku[j]));
然后就是取出最大值。。。輸出
唉，跑的都快超時(shí)了，看看別人0MS過的真是慚愧阿
還有一道50*50的，用這樣的暴力一定過不了，以后要想出更好的辦法
posted on 2009-02-19 14:57
shǎ崽 閱讀(718)
評論(0) 編輯 收藏 引用