HDU4248【DP】

题意:

有n种石头，每种石头有a[i]个，然后让你去组合，问有多少种组合；

思路：

这种题，排列组合知识一上，非常麻烦，已经搞了好几题，看似就是排列组合的姿势，然而最终都是一种递推，也就是DP，而且比较明显的是，基本上这种数的数量级就在100/1000这样。DP来还是很有道理的；

本题：

dp[i][j] 表示前i堆石子构成长度为j的串的方案数；

k代表第 i 堆对于j的使用量，num是当前构成的长度；

然后状态转移就是:dp[i,j]+=dp[i-1,j-k]*C[ k ,num ];

预处理组合数，利用组合的性质：C(n+1,i)=C(n,i)+C(n,i-1);

最后把所有长度的可能性的种类加起来。

#include<stdio.h>

#include<queue>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long LL;

const int INF=0x3f3f3f3f;

//dp[i][j] 表示前i堆石子构成长度为j的串的方案数；

const int N=1e4+10;

const LL mod=1e9+7;

//int num[N];

int num;

LL dp[110][N];

LL C[N][110];

void init()

{

    C[0][0]=1;

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

        for(int j=0;j<=100;j++)

        {

            if(!j)

                C[i][j]=C[i-1][j];

            else

                C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;

        }

}

int main()

{

    init();

    int cas=1;

    int n;

    while(~scanf("%d",&n))

    {

        memset(dp,0,sizeof(dp));

        dp[0][0]=1;

        int sum=0;

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

        {

            scanf("%d",&num);

            sum+=num;

            for(int k=0;k<=num;k++)

                for(int j=k;j<=sum;j++)

                    dp[i][j]=(dp[i][j]+(dp[i-1][j-k]*C[j][k]%mod))%mod;

        }

        LL ans=0;

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

            ans=(ans+dp[n][i])%mod;

        printf("Case %d: ",cas++);

        printf("%lld\n",ans);

    }

    return 0;

}

巴特西

HDU4248【DP】

最新文章

热门文章