Fzu 2204 7【环形Dp----暴力拆分环】

 Problem 2204 7

Accept: 95    Submit: 296 Time Limit: 2000 mSec    Memory Limit : 65536 KB

 Problem Description

n个有标号的球围成一个圈。每个球有两种颜色可以选择黑或白染色。问有多少种方案使得没有出现连续白球7个或连续黑球7个。

 Input

第一行有多组数据。第一行T表示组数。(T <= 20)

每组包含n，表示球的个数。(1 <= n <= 100000)

 Output

每组先输出 "Case #x: " (其中x为当前组数) 该行接下来输出方案数。方案数mod 2015。

 Sample Input

2 7 1

 Sample Output

Case #1: 126 Case #2: 2

 Source

FOJ有奖月赛-2015年10月 思路：

如果其问题不包含环，我们直接设定dp【i】【j】【k】表示到第i个位子，已经有连续j个种类为k的物品连在一起的方案数。

那么其状态转移方程不难推出：

但是因为问题是一个环状的圈而不是一条直线排布，所以在最后统计结果的部分肯定是有有效性的。

而问题只是一个环状的圈 ，所以我们可以暴力的将这个环拆开去处理。

我们枚举起点的状态，长度为1.2.3.4.5.6的两种物品连续摆放，那么在枚举完之后，从下一个位子以另外一种物品作为起点开始Dp.

那么在统计最终结果的时候，如果结尾的物品和开头枚举的物品种类相同，那么只要保证结尾连续的个数+开头连续的个数<7即可。

Dp过程不必要改变，只需要改变一下起点位子和开头状态即可。

Ac代码：

#include<stdio.h> #include<string.h> using namespace std; int dp[100050][10][2]; #define mod 2015 int n,output; int Dp_Slove(int ss,int tmp) { int output=0; memset(dp,0,sizeof(dp)); dp[ss+1][1][1-tmp]=1; for(int i=ss+2; i<=n; i++) { for(int j=1; j<7; j++) { if(j==1) { for(int k=1; k<7; k++) { dp[i][j][0]+=dp[i-1][k][1]; dp[i][j][1]+=dp[i-1][k][0]; dp[i][j][0]%=mod; dp[i][j][1]%=mod; } } else { dp[i][j][0]+=dp[i-1][j-1][0]; dp[i][j][1]+=dp[i-1][j-1][1]; dp[i][j][0]%=mod; dp[i][j][1]%=mod; } } } for(int i=1;i<=6;i++) { for(int j=0;j<=1;j++) { if(j!=tmp) { output+=dp[n][i][j]; output%=mod; } else { if(i+ss<=6) { output+=dp[n][i][j]; output%=mod; } } } } return output; } int main() { int t; int kase=0; scanf("%d",&t); while(t--) { scanf("%d",&n); printf("Case #%d: ",++kase); if(n<=6) { int ans=1; for(int i=1; i<=n; i++)ans*=2; printf("%d\n",ans); } else { output=0; int pre=-1; for(int i=1; i<=6; i++) { for(int j=0; j<=1; j++) { output+=Dp_Slove(i,j); output%=mod; } } printf("%d\n",output); } } }