本文主要是介绍FZU 2200 cleaning (环形dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem 2200 cleaning
Accept: 15 Submit: 27
Time Limit: 1000 mSec Memory Limit : 65536 KB
Problem Description
N个人围成一圈在讨论大扫除的事情，需要选出K个人。但是每个人与他距离为2的人存在矛盾，所以这K个人中任意两个人的距离不能为2，他们想知道共有多少种方法。
Input
第一行包含一个数T(T<=100)，表示测试数据的个数。
接下来每行有两个数N，K，N表示人数，K表示需要的人数(1<=N<=1000,1<=K<=N)。
Output
输出满足题意的方案数，方案数很大，所以请输出方案数mod 1,000,000,007 后的结果。
Sample Input
24 28 3
Sample Output
416
Source
FOJ有奖月赛-2015年10月
题目链接：http://acm.fzu.edu.cn/problem.php?pid=2200
题目分析：又是一道环形dp，这题比之前那个简单一点，因为距离为2的不能一起选，因为是环，直接保留第一个第二个，倒数第一和倒数第二个位置的状态，总空间8e6
设dp[a][b][i][j][x][y]表示第一个人的状态为a第二个人状态为b，前i个人选了j个，第i－1个人的状态为x，第i个人的状态为y的方案数，还是要枚举开头的状态，2*2，一共四种，在线dp的复杂度是4 * n^2，也就是4e6，T是100，时间够呛，所以只好离线预处理，递推的时候四种情况
1.第i－1个没选但是第i个选了，方案数等于第i－1个没选且第i－2个也没选，因为i－1和i－2不能同时选
则有dp[a][b][i][j][0][1] = dp[a][b][i - 1][j - 1][0][0]
2.第i－1个选了且第i个也选了，方案数等于第i－1个选了且第i－2个没选
则有dp[a][b][i][j][1][1] = dp[a][b][i - 1][j - 1][0][1];
3.第i－1个和第i个都没选，则方案数等于第i－1个没选且第i－2个也没选的方案数加上第i－2个选了但是第i－1个没选的方案数的和
则有dp[a][b][i][j][0][0] = dp[a][b][i - 1][j][0][0] + dp[a][b][i - 1][j][1][0]
4.第i－1个选了，第i个没选，则方案数等于第i－1个选了且第i－2个选了的方案数加上第i－1个选了但是i－2个没选的方案数的和
则有dp[a][b][i][j][1][0] = dp[a][b][i - 1][j][0][1] + dp[a][b][i - 1][j][1][1]
最后枚举开头结尾8种状态，去掉开头结尾相接的非法状态，剩余累加即可
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 1e3 + 5;
int const MOD = 1e9 + 7;
int dp[2][2][MAX][MAX][2][2];
int n;void UP(int &x, int y)
{x += y;if(x >= MOD)x -= MOD;
}void cal(int a, int b)
{dp[a][b][2][a + b][a][b] = 1;for(int i = 3; i <= 1000; i++){for(int j = 0; j <= 1000; j++){if(j){dp[a][b][i][j][0][1] = dp[a][b][i - 1][j - 1][0][0];dp[a][b][i][j][1][1] = dp[a][b][i - 1][j - 1][0][1];}UP(dp[a][b][i][j][0][0], dp[a][b][i - 1][j][0][0]);UP(dp[a][b][i][j][0][0], dp[a][b][i - 1][j][1][0]);UP(dp[a][b][i][j][1][0], dp[a][b][i - 1][j][0][1]);UP(dp[a][b][i][j][1][0], dp[a][b][i - 1][j][1][1]);}}
}int main()
{int T;scanf("%d", &T);for(int i = 0; i < 2; i ++)for(int j = 0; j < 2; j ++)cal(i, j);while(T --){int k, ans = 0;scanf("%d %d", &n, &k);for(int i = 0; i < 2; i++)for(int j = 0; j < 2; j++)for(int l = 0; l < 2; l++)for(int z = 0; z < 2; z++)if(!((l == 1 && i == 1) || (z == 1 && j == 1)))UP(ans, dp[i][j][n][k][l][z]);printf("%d\n", ans);}
}这篇关于FZU 2200 cleaning (环形dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
