Problem Description

一把鎖匙有N個(gè)槽，槽深為1，2，3，4。每鎖匙至少有3個(gè)不同的深度且至少有1對相連的槽其深度之差為3。求這樣的鎖匙的總數(shù)。

Input?

本題無輸入

Output

對N>=2且N<=31，輸出滿足要求的鎖匙的總數(shù)。

Sample Input

無?

Sample Output

N=2: 0
N=3: 8
N=4: 64
N=5: 360
..
..
..
..
..
..
..

N=31: ...

注：根據(jù)Pku Judge Online 1351 Number of Locks或 Xi'an 2002 改編,在那里N<=16

思路：一個(gè)遞推的重排列問題，狀壓DP也能做，但還是果斷偷懶用遞推了。。。

用 a[i] 來存儲為?i 個(gè)槽時(shí)的鑰匙數(shù)，假設(shè)一個(gè)鑰匙有 n 個(gè)槽

若該鑰匙的前 n-1 個(gè)槽合法，則第 n 個(gè)槽的深度可為任意深，此時(shí)有 a[n]=4*a[n-1]

若該鑰匙的前?n-1 個(gè)槽不合法，有以下兩種情況：

1）前 n-1 個(gè)有相鄰且相差深度為3的槽，但只有兩種深度，此時(shí)由于有相鄰且相差深度3的槽，因此只能為1、4深度的全排列，再減去只有深度為 1、4 的情況，即有 a[n]=2*(2^(n-1)-2)

2）前 n-1 個(gè)沒有相鄰且相差深度3的槽，由于相差深度為3的槽只有1、4，因此如果想要讓其合法，只有最后一個(gè)排列是1或4時(shí)才可，因此當(dāng)?shù)?n 個(gè)確定時(shí)，第 n-1 個(gè)槽也就確定了

用 b[n-1] 來表示一個(gè) n-1 的排列中符合該種情況且合法的狀態(tài)數(shù)，即用 b[n-1] 表示最后一個(gè)數(shù)是1或4，去掉后這些排列中無相鄰且相差深度為3的槽

由于最后兩個(gè) n、n-1 均可確定，因此前 n-2 個(gè)槽可為任意深度，即有 4^(n-2) 個(gè)，再減去只有深度為 1、4 的情況，即減去 2^(n-2) 個(gè)

此時(shí)，每種情況均可確定，但由于最后 n 位置的槽可能為 1 或 4，因此要乘以 2，再減去前 n-1 項(xiàng)合法的答案即 b[n-1]

即有：a[n]=(2*( 4^(n-2)-2^(n-2) ) )*2-b[n-1]

Source Program

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<set> #include<map> #include<stack> #include<ctime> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 32 #define MOD 10007 #define E 1e-6 #define LL long long using namespace std; LL a[N],b[N]; int main() {a[2]=0;a[3]=8;b[2]=0;b[3]=4;for(int i=2;i<=31;i++){for(int j=4;j<=i;j++){a[i]=4*a[i-1];a[i]+=2*(LL)(pow(2,i-1)-2);a[i]+=2*(LL)(pow(4,i-2)-(LL)pow(2,i-2))-b[i-1];b[i]=2*a[i-1]+2*(LL)(pow(4,i-2)-(LL)pow(2,i-2))-b[i-1];}cout<<"N="<<i<<": "<<a[i]<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的钥匙计数之一（HDU-1483）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。