蓝桥杯【dp?】.cpp

题意：

　　给出一个2*n的方格，当刷完某一个方格的漆后可以且只可以走到相邻的任何一格，即上下左右左上左下右上右下。可以从任意一个格子开始刷墙，问有多少种刷法，因为随着n的增大方案数会变多，因此输出方案数mod 1000000007.

思路：

　　dp[][2], dp[i][0]表示2*i的格子从第i列开始刷，最后回到该格子下面

　　　　　　 dp[i][1]表示2*i的格子从第i列开始刷，最后无法回到该格子下面

　　状态转移方程是：dp[i][0] = 2*dp[i-1][0] 即 A1->B1->...->B2->A2, A1->B2->...->B1->A2, A2也一样

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

因为不能回到那一端，所以一种情况是 1- >2 然后是dp1[i-1]+dp2[i-1]，或者2->1 dp1[i-1]+dp2[i-1]，所以乘以2。

或者可以1->3->2->4，1->4->2->3，2->3->1->4，2->4->1->3，所以乘以4。

初始状态：dp[0][0] = 1, dp[0][1] = 0, dp[1][0] = 2, dp[1][1] = 0;

　　　　　　没有格子的情况下每个子涂所以回到该列只有一种情况，而回不到该列完全不可能。只有一列的情况下回到该列的方案数为2，即A1->A2，或者A2->A1

　　最后罗列出从第一列到最后一列的总共刷墙方案数。

　　ans += 2*((dp[i-1][0]+dp[i-1][1])*dp[n-i][0])) + 2*((dp[n-i)[0]+dp[n-i][1])*dp[i-1][0])

　　　　　　　　即从第i列开始刷，先刷右边的格子，有dp[n-i][0]种方案，因为要刷回来才可以刷左边的格子，然后再刷左边的格子，总共有(dp[i-1][0]+dp[i-1][1])种方案。同理可以先刷左边的格子再刷右边的格子

Tips：

　　nothing？因为公式的推理比较重要..

Code：

 1 #include <stdio.h>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int MAXN = 1010;
 7 const int mod = 1000000007;
 8 
 9 long long dp[MAXN][2];
10 long long ans[MAXN] = {0, 2};
11 
12 void init()
13 {
14     dp[0][0] = 1, dp[0][1] = 0;
15     dp[1][0] = 2, dp[1][1] = 0;
16     for (int i = 2; i < MAXN; ++i) {
17         dp[i][0] = 2*dp[i-1][0]%mod;
18         dp[i][1] = (2*(dp[i-1][0]%mod+dp[i-1][1]%mod)%mod + 4*(dp[i-2][0]%mod+dp[i-2][1]%mod)%mod)%mod;
19     }
20 
21     for (int i = 2; i < MAXN; ++i) {
22         ans[i] = (dp[i][0]%mod+dp[i][1]%mod)%mod;
23         ans[i] = (ans[i]*2)%mod;
24         for (int j = 2; j < i; ++j) {
25             ans[i] += (2*((dp[j-1][0]+dp[j-1][1])%mod*dp[i-j][0]%mod)%mod)%mod;
26             ans[i] += (2*((dp[i-j][0]+dp[i-j][1])%mod*dp[j-1][0]%mod)%mod)%mod;
27         }
28         ans[i] %= mod;
29     }
30 
31 }
32 
33 int main()
34 {
35     int n;
36     init();
37     while (~scanf("%d", &n)) {
38         printf("%lld
", ans[n]);
39     }
40     return 0;
41 }

View Code

链接：http://acm.nbut.cn/Problem/view.xhtml?id=1476

蓝桥杯 【dp?】.cpp

蓝桥杯【dp?】.cpp