题目链接

【题意】

有两种元素U和L，要求把n个元素排成一行同时要求至少有3个U在一起，问有多少种方法？当n=4,5,30时答案分别为3,8,974791728

【思路】

每个位置不是放U就是放L，所以总情况数是 2n2n，那么用总情况数减去最多有两个连续U的情况数就是答案了.

设 dp[n][0]dp[n][0] 和 dp[n][1]dp[n][1] 分别代表长度为n的序列以L为结尾和以R为结尾的至多两个连续U的情况数

那么不难想到状态转移

dp[n][0]=dp[n−1][0]+dp[n−1][1]dp[n][0]=dp[n−1][0]+dp[n−1][1]

dp[n][1]=2dp[n−2][0]+dp[n−2][1]dp[n][1]=2dp[n−2][0]+dp[n−2][1]

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int maxn=33;int n;int dp[maxn][2];int main(){    dp[1][0]=dp[1][1]=1;    dp[2][0]=dp[2][1]=2;    for(int i=3;i<=30;++i){        dp[i][0]=dp[i-1][0]+dp[i-1][1];        dp[i][1]=dp[i-2][1]+dp[i-2][0]*2;    }    while(scanf("%d",&n)==1 && n){        int ans=1<