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