DP-递推-POJ-1285-Combinations, Once Again

最新推荐文章于 2025-04-09 14:15:04 发布

STL_CC

最新推荐文章于 2025-04-09 14:15:04 发布

阅读量215

点赞数

分类专栏： ACM赛题与杂谈文章标签：算法动态规划 acm竞赛 icpc 背包

本文链接：https://blog.csdn.net/STL_CC/article/details/105670629

版权

ACM赛题与杂谈专栏收录该内容

6 篇文章

订阅专栏

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const ll maxn=55;
ll dp[maxn][maxn];
ll num[maxn];
ll m,n,T=1,x;
int main()
{
    while(scanf("%lld%lld",&n,&m)&&n)
    {
        memset(num,0,sizeof(num));
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
        {
            scanf("%lld",&x);
            num[x-1]++;
        }
        for(int i=0;i<=num[0];i++)
        {
            dp[0][i]=1;
        }
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<=n;j++)
            {
                for(int k=0;k<=num[i]&&k<=j;k++)
                {
                    dp[i][j]+=dp[i-1][j-k];
                }
            }
        }
        printf("Case %d:\n",T++);
        for(int i=0;i<m;i++)
        {
            scanf("%lld",&x);
            printf("%lld\n",dp[n-1][x]);
        }
    }
    return 0;
}