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

poj3254(Corn Fields)狀壓dp

編輯:C++入門知識

題意:在n*m(1<=n,m<=12)的矩陣上種植玉米,任意共邊的方格不能同時種,並且有些特定方格也不能種。問能有多少種種植的方案;


解法;很經典的狀壓模型。先將每一行的合法狀態求出來,12的時候最多377個合法狀態。然後進行與行之間的狀態轉移。最壞復雜度12*(377^2)


代碼:

/****************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define eps 1e-8
typedef long long LL;

int inf= 100000000;
int rem[15][15];
int legal[10000];
int p=0;
int n,m;
int num[20];
bool OK(int k)
{
    return !(k&(k<<1));
}
int ans[20][10000];
int main()
{
  scanf("%d%d",&n,&m);
  for(int i=0;i

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