HDU1267 递推

题目链接

题意：给定m个H和n个D(1<=n,m<=20)，问这些字母构成的序列中，对于任意位置，从左开始数H的累积个数总是不比D的累计数少的排列有多少种。

题解：二维DP，画一个正方形，从左上角到右下角画一条线，右上方区域就是我们所要求的。另外注意这个题的输入顺序是先输入m再输入n。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll dp[][];

int n,m;

void init()

{

    memset(dp,,sizeof(dp));

    for(int j=; j<=; j++) dp[][j]=;

    for(int i=; i<=; i++)

        for(int j=i; j<=; j++)

            dp[i][j]=dp[i-][j]+dp[i][j-];

}

int main()

{

    init();

    while(cin>>m>>n)

        cout<<dp[n][m]<<endl;

    return ;

}

虽然知道深搜2^40会超时，但还是用深搜写了一发。

#include <bits/stdc++.h>

using namespace std;

int n,m,x,ans,data[];

void dfs(int k,int n,int m)

{

    if(k==x)

    {

        int tmp=;

        for(int i=; i<k; i++)

        {

            tmp+=data[i];

            if(!data[i]) tmp--;

            if(tmp<) return;

        }

        if(tmp>=)

        {

            //for(int i=0; i<k; i++) printf("%d ",data[i]);

            //printf("*\n");

            ans++;

        }

        //memset(data,0,sizeof(data));

        return;

    }

    if(n>)

    {

        data[k]=; n--;

        dfs(k+,n,m);

        n++;//这个一定要放到里面

    }

    if(m>)

    {

        data[k]=; m--;

        dfs(k+,n,m);

        m++;

    }

}

int main()

{

    while(cin>>m>>n)

    {

        memset(data,,sizeof(data));

        x=n+m;

        ans=;

        dfs(,n,m);

        cout<<ans<<endl;

    }

    return ;

}

貌似这道题还可以用公式算：传送门。