程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3254 Corn Fields 狀態壓縮dp

poj 3254 Corn Fields 狀態壓縮dp

編輯:C++入門知識

poj 3254 Corn Fields 狀態壓縮dp


題意:

給一塊m行n列的土地,有一些格可以種樹,另外一些不可以,樹不能相鄰,問一共有多少種種法。

分析:

從後往前種,子問題向父問題擴展,當種到某一格時只有他和他後面的n-1個格子的情況對它有影響,故對這n個格子進行編碼為狀態S,表示種完(多米諾骨牌那題是放置前,注意區別,都可行)這n個格子的狀態。父問題由稍小子問題逐步解決,正是動態規劃的思想。

代碼:

//poj 3254
//sep9
#include 
using namespace std;
const int maxN=14;
const int mod=100000000;
int land[maxN][maxN];
int dp[2][1<=0;--i)
		for(j=n-1;j>=0;--j){
			for(used=0;used<1<>j&1)
						nxt[used]=0;
					else{
						nxt[used]=cur[used];
						nxt[used]+=cur[used|(1<>j&1)&&(used>>(j+1)&1)){
						res=0;
					}else if(!(used>>j&1)&&(used>>(j+1)&1)){
						res=cur[used];
						res+=cur[used|(1<>j&1)&&!(used>>(j+1)&1)){
						res=cur[used&(~(1<>j&1)&&!(used>>(j+1)&1)){
						res=cur[used];
						res+=cur[used|(1<

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved