fzu 2204 7 dp

题目链接：

题目描述：

　　给出n个小球，每个小球只能涂黑色或者是白色，七个连续的不能是同种颜色，问有多少种涂色方法？

解题思路：

　　刚开始没有考虑到是环形的，WA的风生水起，怪我咯！怪我咯！最后看到是环形的，然后就考虑去除环的影响。

　　先设定起始位置小球颜色为0(白色), (1-->黑色)，考虑可知起始位置小球颜色为1的方案数目与设定方案相同，所以算出任意一种，乘上2就是答案。

　　dp[a][x][y] 代表 a-->前a个小球颜色都为0, x-->第i位置小球的颜色, y-->当前位置为y, dp[x][y]-->当前状态的摆放方案数目。第一维与后面的两维是独立的，没有什么因果关系，讷，现在我们把第一维删掉，然后对后面两维循环6次即可。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 const int mod = ;

 int dp[][maxn];

 int main ()

 {

     int T, n;

     scanf ("%d", &T);

     for (int t=; t<=T; t++)

     {

         scanf ("%d", &n);

         int ans = ;

         for (int start=; start<; start++)

         {

             memset (dp, , sizeof(dp));

             dp[][start] = ;

             for (int i=start+; i<=n; i++)

             {

                 for (int j=; j<; j++)

                 {

                     if (i==n && j == )

                     {

                         for (int k=; k<=-start; k++)

                             if (i > k)

                                 dp[j][i] += dp[-j][i-k];

                         dp[j][i] = dp[j][i] % mod;

                     }

                     else

                     {

                         for (int k=; k<=; k++)

                             if (i > k)

                             dp[j][i] += dp[-j][i-k];

                         dp[j][i] = dp[j][i] % mod;

                     }

                 }

             }

             ans = (ans + dp[][n] + dp[][n]) % mod;

         }

         printf ("Case #%d: %d\n", t, (ans * ) % mod);

     }

     return ;

 }

巴特西

fzu 2204 7 dp

最新文章

热门文章