FZU 2204 7 (环形dp)

本文主要是介绍FZU 2204 7 (环形dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.fzu.edu.cn/problem.php?pid=2204

题目分析：乍一看以为是组合数学推公式，其实这东西叫环形dp，如果是在一条线上会简单很多，在环上的话要注意开头和结尾相接的情况，因此可以枚举开头的状态

设dp[fir][i][j][k]表示颜色是0的开头位置为dir的第i个位置为j颜色(0/1)且其之前k个位置都是j颜色的方案数，递推的时候有两种情况。

1.第i个位置变色，那有dp[fir][i][j][0] += dp[fir][i - 1][j ^ 1][k]，表示前一个位置和当前位置的颜色不同，当然前6个位置都可以与当前的不同

2.第i个位置不变色，则dp[fir][i][j][k] += dp[fir][i - 1][j][k - 1]，这个不解释了

可以离线预处理出所有情况，复杂度O(7 * 2 * 6  * 1e5)，查询的时候如果n小于7，直接2^n，否则累加颜色为0开头位置为1,2,3,4,5,6的6种情况的方案数，如果末尾为0的话，判断一下加上开头连续0的长度是不是小于7，是的话要加上这种情况，最后乘2，因为开头状态可以是黑也可以是白

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int const MAX = 1e5 + 5;
int const MOD = 2015;
int dp[7][MAX][2][6];
int n, ans;void UP(int &x, int y)
{x += y;if(x >= MOD)x -= MOD;
}void pre()
{for(int fir = 1; fir < 7; fir ++){dp[fir][fir + 1][1][0] = 1;for(int i = fir + 2; i <= 100000; i++){for(int j = 0; j < 2; j++){for(int k = 0; k < 6; k++){   UP(dp[fir][i][j][0], dp[fir][i - 1][j ^ 1][k]);if(k)UP(dp[fir][i][j][k], dp[fir][i - 1][j][k - 1]);}}}}
}int main()
{pre();int T;scanf("%d", &T);for(int ca = 1; ca <= T; ca++){   scanf("%d", &n);if(n < 7){printf("Case #%d: %d\n", ca, (int) pow(2.0, n));continue;}ans = 0;for(int fir = 1; fir < 7; fir++){for(int i = 0; i < 6; i++){if(i + 1 + fir < 7)UP(ans, dp[fir][n][0][i]);UP(ans, dp[fir][n][1][i]);}}UP(ans, ans);printf("Case #%d: %d\n", ca, ans);}
}

这篇关于FZU 2204 7 (环形dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---