题目1552：座位问题

题目1552：座位问题

时间限制：1秒

内存限制：32 兆

特殊判题：否

提交：373

解决：120

 

题目描述：

计算机学院的男生和女生共n个人要坐成一排玩游戏，因为计算机的女生都非常害羞，男生又很主动，所以活动的组织者要求在任何时候，一个女生的左边或者右边至少有一个女生，即每个女生均不会只与男生相邻。现在活动的组织者想知道，共有多少种可选的座位方案。

例如当n为4时，共有
女女女女, 女女女男, 男女女女, 女女男男, 男女女男, 男男女女, 男男男男
7种。

输入：

输入包含多组测试用例，每组测试用例仅包含一个整数n(1<=n<=1000)。

输出：

对于每组测试用例，输出一个数代表可选的方案数，为防止答案过大，答案对1000000007取模。

样例输入：

　　1
　　2
　　4

 

 

样例输出：

　　 1
　　 2
　　 7

 

 

 

法一:状态f[i][0]表示第i的位置为男生的i个人总的排座方式，f[i][1]表示第i的位置为女生的i个人总的排座方式。

#include<stdio.h>
const int MAXN=1001;
const int M=1000000007;
int f[1001][2];
int dp()
{
    f[0][0]=1;
    f[1][0]=1;
    f[1][1]=0;
    int sum=0;
    for (int i=2;i<MAXN;i++)
    {
        f[i][0]=(f[i-1][0]+f[i-1][1])%M;
        sum=sum+f[i-2][0];
        sum=sum % M;
        f[i][1]=sum;
    }
    return 0;    
}
int main()
{
    dp();
    int n;
    while(scanf("%d",&n)!=EOF)
        printf("%d
",(f[n][0]+f[n][1])%M);
    return 0;
}

这是另一种方法，但是感觉不对，如何证明？