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; 
}