首页 > 代码库 > hdu1297 Children’s Queue

hdu1297 Children’s Queue

加一个男的:dp[i-1];

加2个女的:dp[i-2]+x;

上面第二种情况中的dp[i-2]只包含了未加2个女的就合法的情况,而x就是不合法情况,即最后为mf的情况,则x=dp[i-4](后面跟mfff);

这题要用大数;

#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(void)
{
    int n;
    int dp[1001][101]={0};
    dp[0][1]=1;
    dp[1][1]=1;
    dp[2][1]=2;
    dp[3][1]=4;
    for(int i=4; i<1001; i++)
    {
        for(int j=1; j<100; j++)
        {
            dp[i][j]+=dp[i-1][j]+dp[i-2][j]+dp[i-4][j];
            dp[i][j+1]+=dp[i][j]/10000;
            dp[i][j]%=10000;
        }
    }
    while(scanf("%d",&n)!=EOF)
    {
        int k=100;
        while(!dp[n][k])
            k--;
        printf("%d",dp[n][k--]);
        while(k)
        {
            printf("%04d",dp[n][k--]);
        }
        puts("");
    }
    return 0;
}


hdu1297 Children’s Queue