"红色病毒"问题 HDU 2065 递推+找循环节

题目连接:

http://acm.hdu.edu.cn/showproblem.php?pid=2065

递推类题目, 可以考虑用数学方法来做, 但是明显也可以有递推思维来理解。

递推的话基本就是状态转移了, 如何找状态是递推的关键。

我们把这个分为四个状态

A 出现次数的奇偶和B出现状态的奇偶,我们可以构造出四个状态:

A        B

第一个状态 :        偶       偶     0

第二个状态 :        偶       奇     1

第三个状态 :        奇       偶     2

第四个状态 :        奇       奇     3

我们由这些状态进行转移 设定数组  dp[第k个状态][字符串的长度n]

进行状态转移:

偶偶  <-    偶 奇  +  偶偶  + 奇偶

依次类推........

dp[0][i] = (dp[0][i-1]*2 + dp[1][i-1] + dp[2][i-1]);
dp[1][i] = (dp[1][i-1]*2 + dp[0][i-1] + dp[3][i-1]);
dp[2][i] = (dp[2][i-1]*2 + dp[0][i-1] + dp[3][i-1]) ;
dp[3][i] = (dp[3][i-1]*2 + dp[1][i-1] + dp[2][i-1]) ;

得到四个状态转移方程

dp[0][i-1]*2 是因为 无论是 第i个 字符是A  或者是 B 对下一个状态都 无影响。

他们给我们的数字是非常大的, 因此我们要去找循环节。

循环节是20个数字  一个循环, 但是前两个数字不在循环内部 要特殊处理

下面是代码:

 #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
#include<string>
#include<queue>
using namespace std;
const int maxn = ;
const long long INF = 0xfffffff; int main()
{
int dp[][maxn] ={};
int P[maxn];
dp[][] = ;
for(int i=; i<=; i++)
{
dp[][i] = (dp[][i-]* + dp[][i-] + dp[][i-]) % ;
dp[][i] = (dp[][i-]* + dp[][i-] + dp[][i-]) % ;
dp[][i] = (dp[][i-]* + dp[][i-] + dp[][i-]) % ;
dp[][i] = (dp[][i-]* + dp[][i-] + dp[][i-]) % ;
// cout << dp[0][i] << endl;
if(i > )
P[i-] =dp[][i];
}
int T, cas; long long n;
while(cin >> T, T)
{
cas = ;
while(T--)
{
cin >> n;
cout << "Case "<<cas++<<": "; if(n < )
cout<<dp[][n]<<endl;
else
cout<<P[(n-)%]<<endl; if(!T)
cout << endl;
}
}
return ;
}
上一篇:HDOJ(HDU).2044-2049 递推专题


下一篇:HDU 2842 (递推+矩阵快速幂)