Children’s Queue HDU 1297 递推+大数

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1297

题目大意：

有n个同学，站成一排，要求女生最少是两个站在一起，问有多少种排列方式。

题目分析：

1. 假设第n个学生是个男生，我们可以直接将他放在最后有 dp[n-1]种

即： ...............M dp[n-1]

2.假设第n个放女生，要求两个女生在一起，我们可以直接在最后放两个女生

即： .............FF dp[n-2]

3.假设我们后面放两个女生，但之前的序列最后两个是一个男生+一个女生即： ...........MF 序列

明显是不合法的，但是我们后面要是再加上两个女生就能使这个原来不合法的序列变的合法

即 ................MF FF dp[n-4]

综上：我们的递推式子为： dp[n] = dp[n-1] + dp[n-2] + dp[n-4];

因为数据量为1000 所以我们用大数来进行运算

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stack>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
const long long  maxn =1005;
const long long  INF = 0xfffffff;
int dp[maxn][maxn];
void Slove()
{
    dp[0][0] = 1;
    dp[1][0] = 1;
    dp[2][0] = 2;
    dp[3][0] = 4;
    for(int i=4; i<maxn; i++)
    {
        for(int j=0; j < maxn; j++)
        {
            dp[i][j] += dp[i-1][j] + dp[i-2][j] + dp[i-4][j];
            dp[i][j+1] += dp[i][j]/10;
            dp[i][j] %= 10;
        }
    }
}

void Putt(int n)
{
    int i;
    for(i = maxn - 1; i >= 0; i--)
        if(dp[n][i])
         break;

    for(; i>0; i--)
        printf("%d",dp[n][i]);
    printf("%d
",dp[n][i]);
}
int main()
{
    int n;
    Slove();
    while(cin >> n)
    {
        Putt(n);
    }
    return 0;
}

Children’s Queue HDU 1297 递推+大数

相关推荐