Description
小松鼠开心地在树之间跳跃着，突然她停了下来。因为眼前出现了一个 拿着专克超萌小松鼠的法宝————超萌游戏机的游客！ 超萌游戏机之所以拥有这个名字，是因为它的屏幕是一个n × 2的矩形。 小松鼠接过游戏机，开始了她的第一个游戏：俄罗斯方块。 考虑到小松鼠的智商，游戏机里的方块只有下面四种，方块按顺序下落，
* * **
** ** ** *
* * ** *
（我尽力了） 可以在任意时刻（甚至是下落前）对其进行不限次数的旋转操作。 由于四种方块最小宽度都为2，因此下落的时候在水平方向上是不能够移 动的。我们称当前方块下落的过程完成了，当且仅当其再往下移动一个单 位就会与之前覆盖的方块有部分相重叠。小松鼠想要知道，在这个n×2的 游戏界面中，一共会出现多少种游戏状态。游戏状态指单次方块下落的过 程完成后，不要求游戏结束（即不要求第1行非空），且界面中出现的必须 是完整的方块。 两种游戏状态被认为是相同的，当且仅当游戏界面中的每一个格子两种 状态下被覆盖的方块类型都相同（或都不被覆盖）。 再次考虑到小松鼠的智商，答案模109 + 7 输出。
一行一个数n，表示游戏界面的长度。
Output
一个数，表示游戏界面的状态数在模109 + 7意义下的值。
Constraints
对于前10%，n <= 10。 对于前30%，n <= 1000。 对于前60%，n <= 100000。 对于100%，n <= 1000000。
Code
#include <cstdio>
#include <cstring>
#include <queue>
#define INF 100000000
#define maxn 100000
#define mo 1000000007
using namespace std;
int n;
long long dp[
1001000][
7],ans=
0;
int main(){
scanf(
"%d",&n);
memset(dp,
0,
sizeof(dp));
for(
int i=
1;i<=
6;i++) dp[
3][i]=
1;
dp[
3][
4]=
0; dp[
2][
4]=
1;
for(
int i=
4;i<=n;i++){
dp[i][
1]=(dp[i-
3][
1]+dp[i-
2][
2]+dp[i-
2][
3]+dp[i-
3][
4]+dp[i-
2][
5]+dp[i-
3][
6])%mo;
dp[i][
2]=(dp[i-
2][
1]+dp[i-
3][
2]+dp[i-
3][
3]+dp[i-
3][
4]+dp[i-
3][
5]+dp[i-
3][
6])%mo;
dp[i][
3]=(dp[i-
3][
1]+dp[i-
2][
2]+dp[i-
2][
3]+dp[i-
3][
4]+dp[i-
2][
5]+dp[i-
3][
6])%mo;
dp[i][
4]=(dp[i-
2][
1]+dp[i-
2][
2]+dp[i-
2][
3]+dp[i-
2][
4]+dp[i-
2][
5]+dp[i-
2][
6])%mo;
dp[i][
5]=(dp[i-
3][
1]+dp[i-
3][
2]+dp[i-
3][
3]+dp[i-
3][
4]+dp[i-
3][
5]+dp[i-
3][
6])%mo;
dp[i][
6]=(dp[i-
3][
1]+dp[i-
2][
2]+dp[i-
2][
3]+dp[i-
3][
4]+dp[i-
1][
5]+dp[i-
3][
6])%mo;
}
for(
int i=
2;i<=n;i++)
for(
int j=
1;j<=
6;j++)
ans+=dp[i][j]%mo;
printf(
"%lld",(ans+
1)%mo);
return 0;
}
转载于:https://www.cnblogs.com/leotan0321/p/6081378.html
相关资源：数据结构—成绩单生成器
