程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 12446 How Many... in 3D! 搭積木 dp

UVA 12446 How Many... in 3D! 搭積木 dp

編輯：C++入門知識

UVA 12446 How Many... in 3D! 搭積木 dp

題目鏈接：點擊打開鏈接

題意：

用1*1*2的方塊搭出2*2*N的方塊的方法數

則對於每一層有9種狀態

0、全為1.

1、

0表示這個為空，__表示這兩個平躺著一個方塊

2、

0表示這格為空，1表示這格方塊是直立放著的。

如此類推除第0種共8種狀態，然後就是簡單的轉移。

而其他狀態是無效的，不會參與到答案的計算中，所以不需要考慮

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
template 
inline bool rd(T &ret) {
	char c; int sgn;
	if(c=getchar(),c==EOF) return 0;
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
template 
inline void pt(T x) {
    if (x <0) {
        putchar('-');
        x = -x;
    }
    if(x>9) pt(x/10);
    putchar(x%10+'0');
}

using namespace std;
const int N = 1000100;
const int mod = 1000*1000*1000+7;
void add(const int &y,int& x){
	x += y;
	if(x >= mod) x-=mod;
}
int d[N][9];
int main() {
	memset(d, 0, sizeof d);
	d[0][0] = 1;

	for(int i = 0; i < N-1; i++)
	{
		add(d[i][1], d[i][0]);
		add(d[i][2], d[i][0]);
		add(d[i][4], d[i][0]);
		add(d[i][5], d[i][0]);
		add(d[i][6], d[i][0]);
		add(d[i][8], d[i][0]);
		
		if(i>1)add(d[i-2][0], d[i][0]);
		
		add(d[i][0], d[i+1][1]);
		add(d[i][0], d[i+1][3]);
		add(d[i][0], d[i+1][5]);
		add(d[i][0], d[i+1][7]);
		
		
		add(d[i][1], d[i+1][4]);
		add(d[i][2], d[i+1][4]);
		add(d[i][3], d[i+1][2]);
		add(d[i][4], d[i+1][2]);
		
		add(d[i][5], d[i+1][8]);
		add(d[i][6], d[i+1][8]);
		add(d[i][7], d[i+1][6]);
		add(d[i][8], d[i+1][6]);
		
	}
	int T, n;scanf("%d", &T);
	while(T--){
		scanf("%d", &n);
		printf("%d\n", d[n][0]);
	}
	return 0;
}