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

poj 2411 Mondriaan's Dream(狀壓DP)

編輯:C++入門知識

poj 2411 Mondriaan's Dream(狀壓DP)


Mondriaan's Dream Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 12232 Accepted: 7142

Description

Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.
\

Expert as he was in this material, he saw at a glance that he"ll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won't turn into a nightmare!

Input

The input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.

Output

\For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is Z喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcmllbnRlZCwgaS5lLiBjb3VudCBzeW1tZXRyaWNhbAogdGlsaW5ncyBtdWx0aXBsZSB0aW1lcy4KPHAgY2xhc3M9"pst">Sample Input

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

Sample Output

1
0
1
2
3
5
144
51205

Source

Ulm Local 2000



思路和(前一篇文章)SGU 131 一樣,這種類型題目關鍵就是要學會如何去枚舉狀態,以及狀態的轉移。


#include 
#include 
#include 
#define LL long long
using namespace std;
const int N=12;

LL dp[N][1<m)
    {

        if(!b1 && !b2)  dp[x][s1]+=dp[x-1][s2];
        return ;
    }
    if(!b1 && !b2)  dfs(x,y+1,s1*2+1,s2*2,0,0);
    if(!b1)         dfs(x,y+1,s1*2+1,s2*2+1-b2,1,0);
    dfs(x,y+1,s1*2+b1,s2*2+1-b2,0,0);
}

void initial()
{
    len=1<

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