fzu2200 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

Source

FOJ有奖月赛-2015年10月

这题可以用dp做，费了不少时间。。我们可以预处理出答案，枚举第一个与第二个的情况，然后设dp[i][j][k]表示当前循环到i，已经选了j个，最后两位的状态为k所对应的二进制状态，k=0,1,2,3,0表示当前这个和前面一个都没取，1表示当前这个没取，前面取了。

然后i就可以从3开始转移了，这里要注意，dp[2][1]的方案数要看做0。

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<string>

#include<algorithm>

using namespace std;

typedef long long ll;

#define inf 0x7fffffff

#define maxn 1006

ll rear[maxn][maxn];

ll dp[maxn][maxn][4];

#define MOD 1000000007LL

void init()

{

    int i,j,ii,jj,a;

    memset(rear,0,sizeof(rear));

    for(ii=0;ii<2;ii++){

        for(jj=0;jj<2;jj++){

            memset(dp,0,sizeof(dp));

            dp[2][0][ii+jj*2]=1;

            for(i=3;i<=1002;i++){

                for(j=0;j<=i;j++){

                    for(a=0;a<4;a++){

                        if(a%2==0){

                            dp[i][j][0]=(dp[i][j][0]+dp[i-1][j][a])%MOD;

                        }

                        if(a==0 && j){

                            dp[i][j][1]=(dp[i][j][1]+dp[i-1][j-1][a])%MOD;

                        }

                        if(a%2==1){

                            dp[i][j][2]=(dp[i][j][2]+dp[i-1][j][a])%MOD;

                        }

                        if(a==1 && j){

                            dp[i][j][3]=(dp[i][j][3]+dp[i-1][j-1][a])%MOD;

                        }

                    }

                    for(a=0;a<4;a++){

                        if( (a^(ii+jj*2))==0){

                            rear[i-2][j]=(rear[i-2][j]+dp[i][j][a])%MOD;

                        }

                    }

                }

            }

        }

    }

}

int main()

{

    init();

    ll t;

    scanf("%I64d",&t);

    while(t--)

    {

        ll n,kk;

        scanf("%I64d%I64d",&n,&kk);

        int ans=0;

        printf("%I64d\n",rear[n][kk]%MOD);

    }

    return 0;

}

巴特西