HDU 1297 Children’s Queue （DP）

分男女生考慮，設總共有n個人(f(n)表示當有n個人的時候合法序列的個數，ak表示第k個人)，當a1為男生時，有f(n-1)種可能，當a1是女生時，a2必為女生；當a1、a2都為女生時，a3為男生，有f(n-3)種可能，當a1、a2、a3都為女生，a4為男生時，有f(n-4)種可能，以此類推（下式中1表示n全為女生時那種情況，規定f(0) = 1）, 故有 f(n) = f(n-1) + f(n-3) + f(n-4) + f(n-5) + ... + f(1) + f(0) + 1; 所以 f(n-2) = f(n-3) + f(n-5) + f(n-6) + ... + f(1) + f(0) + 1; 由以上兩式得 f(n) = f(n-1) + f(n-2) + f(n-4)

[csharp]
#include"stdio.h"
#include"string.h"
int f[1001][300];
int main()
{
    int i,j,n;
    int temp;
    memset(f,0,sizeof(f));
    f[0][0]=1;
    f[1][0]=1;
    f[2][0]=2;
    f[3][0]=4;
    for(i=4;i<=1000;i++)
    {
        temp=0;
        for(j=0;j<300;j++)
        {
            f[i][j]= f[i-1][j] + f[i-2][j] + f[i-4][j] + temp;
            temp=f[i][j]/10;
            f[i][j]%=10;
        }
    }
    int flag;
    while(scanf("%d",&n)!=EOF)
    {
        flag=0;
        for(j=299;j>=0;j--)
        {
            if(f[n][j]!=0) flag=1;
            if(flag==1)
                printf("%d",f[n][j]);
        }
        printf("\n");
    }
    return 0;
}

补充：软件开发 , C# ,