不安全字符串
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 5 Accepted Submission(s) : 4
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
集训十分无聊，于是boss发明了一个“益智”游戏——假设有一段仅由U和L构成的字符串，我们定义当连续的U的个数大于等于三的时候，这个字符串是不安全的。现告诉你字符串的长度n,请你算出能够生成多少个不安全字符串。Input
输入有多组，每组仅输入一个n，代表字符串的长度,当n等于0的时候输入结束。（4<=n<=30）Output
输出可生成的不安全字符串的个数。Sample Input
4 5 0Sample Output
3 8 Hint:对于第一个样例，当n为4的时候，我们满足条件的有 UUUU LUUU UUUL 三种情况
思路：递推吧，因为每一个情况都是由前一个情况转变过来的，所以用一个dp数组去存每个情况相应的值，每一层的意思如下：（i为当前序列的长度）
dp[i][0]没有三个连续U的序列最右边为L
dp[i][1]没有三个连续U的序列最右边有一个U
dp[i][2]没有三个连续U的序列最右边有两个连续的U
dp[i][3]有三个连续的U的序列
结合每个情况可以发现
- dp[i][0]可以由dp[i-1][0]+dp[i-1][1]+dp[i-1][2]转变过来，因为前一状态只要不是有了3个连续的U的序列，在最右边加一个L就可以形成
- dp[i][1]可以由dp[i - 1][0]转变过来，因为只能是在最右边没有U的序列加上个U形成
- dp[i][2]可以由dp[i - 1][1]转变过来，因为只能是在最右边有一个U的序列加上个U形成
- dp[i][3]可以由dp[i - 1][3] * 2 + dp[i - 1][2]转变过来，因为如果原本就是有连续3个U的序列最右边加上什么都是该情况，然后也可以在最右边有两个U的序列加上个U形成
结合上面的思路就能写出这题了
ps：这是题解：http://blog.csdn.net/xjh_shin/article/details/76303921
AC代码：
1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 long long dp[100][5]; 5 int main() 6 { 7 dp[1][0]=1; 8 dp[1][1]=1; 9 dp[1][2]=0; 10 dp[1][3]=0; 11 for(int i=2;i<50;i++) 12 { 13 dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]; 14 dp[i][1]=dp[i-1][0]; 15 dp[i][2]=dp[i-1][1]; 16 dp[i][3]=dp[i-1][3]*2+dp[i-1][2]; 17 } 18 int n; 19 while(~scanf("%d",&n)){ 20 if(n==0) break; 21 else{ 22 cout<<dp[n][3]<<endl; 23 } 24 } 25 return 0; 26 }