UVA580-Critical Mass

题目链接

题意：一个栈中只能放入U和L，问存在连续3个以上U(危险组合)的个数为几个

思路：用从的组合数-安全组合=危险组合。d[i]表示第i个位置以L结束的序列，所以就有d[i] = d[i - 1] + d[i - 2] + d[i - 3]。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int MAXN = 55; int dp[MAXN]; int n; void init(){ memset(dp, 0, sizeof(dp)); dp[1] = 2; dp[2] = 4; dp[3] = 7; for (int i = 4; i < MAXN; i++) dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; } int main() { init(); while (scanf("%d", &n) && n) { int ans = pow(2, n); ans -= dp[n]; printf("%d\n", ans); } return 0; }