题目链接：

思路：

这道题是维基百科上面的记忆化搜索的例题。。。
四维状态dp[maxn][5][2][5]分别表示第几根棒子，这根棒子的高度，是否达到题目的要求和使用不同棒子数，那么接下来就是状态转移了。。。要用到位运算判断以前是否这种高度的棒子用到没。。。那么这个问题就解决了。。。

Description

Input

Output

Sample Input

2
3
-1

Sample Output

2: 0
3: 8

Source

#include
   
    
#include
    
      #include
     
       #define New (1<<(d-1)) using namespace std; const int maxn=17+10; long long dp[maxn][5][2][5]; int n; long long dfs(int ith,int height,int k,int use,int s) { if(dp[ith][height][k][use]!=-1) return dp[ith][height][k][use]; if(ith==n) { if(k&&use>=3) return 1; else return 0; } long long ans=0; int tmp; for(int d=1;d<=4;d++) { if(!(s&New)) tmp=use+1; else tmp=use; // tmp=min(use,3); if(k||(d*height==4&&d!=2)) ans=ans+dfs(ith+1,d,1,tmp,s|New); else ans=ans+dfs(ith+1,d,0,tmp,s|New); } return dp[ith][height][k][use]=ans; } int main() { while(~scanf("%d",&n)) { if(n==-1) return -1; printf("%d: ",n); memset(dp,-1,sizeof(dp)); if(n<3) puts("0"); else { dfs(0,0,0,0,0); printf("%lld\n",dp[0][0][0][0]); } } return 0; }