本文主要是介绍FOJ 2200 cleaning(环形dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem 2200 cleaning
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
先考虑一下线性的，环其实就是直线的一种变形，
dp[i][j]表示前i个人取j个人的情况，则dp[i][j]=dp[i-1][j]+dp[i-4][j-2]+dp[i-3][j-1];
//dp[i-1][j]表示不选第i个人
//dp[i-4][j-2]表示选第i和i-1个人,不选第i-2个人
//dp[i-3][j-1]表示选第i个人,不选第i-1和i-2
接下来变线成环，就是第1个和第n个合在一起了
(1)当1，n都不选时,为dp[n-2][k];
(2)当1,n都选时,为dp[n-6][k-2]
(3)当选1不选n时，这种情况要考虑下第2个选不选，总的为dp[n-6][k-2]+dp[n-5][k-1]
(4)当选n不选1时，与(3)是一样的;
AC代码：
# include <stdio.h>
# include <string.h>
typedef long long int ll;
const int mod=1000000007;
int dp[1010][1010];
int a[10][10];
int main(){int i, j, k, n, t;memset(dp, 0, sizeof(dp));dp[1][0]=dp[1][1]=dp[0][0]=1;dp[2][0]=1;dp[2][1]=2;dp[2][2]=1;dp[3][0]=1;dp[3][1]=3;dp[3][2]=2;for(i=4; i<=1000; i++){dp[i][0]=1;dp[i][1]=i;for(j=2; j<=i; j++){dp[i][j]=((dp[i-1][j]+dp[i-4][j-2])%mod+dp[i-3][j-1])%mod;}}a[1][1]=1;a[2][1]=1;a[2][2]=1;a[3][1]=3;a[3][2]=3;a[4][1]=4;a[4][2]=4;a[5][1]=1;a[5][2]=5;scanf("%d", &t);while(t--){scanf("%d%d", &n, &k);if(n<6){printf("%d\n", a[n][k]);continue;}ll ans=0;ans=ans+dp[n-2][k];ans=ans+dp[n-6][k-2];ans=ans+dp[n-6][k-2]+dp[n-5][k-1];ans=ans+dp[n-6][k-2]+dp[n-5][k-1];printf("%d\n", (int)(ans%mod));}return 0;
}这篇关于FOJ 2200 cleaning(环形dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
