题目描述

现在有 n 个物品（有可能相同），请编程计算从中取 k 个出来， 有多少种不同的取法。

输入

输入文件有两行。
第一行包含两个整数 n,k(2<=n<=30,0<=k<=n) 。
第二行包含 n 个整数， 表示物品的编号（范围 1..1000）。编号相同的物品看作同一种物品。

输出

输出仅一行一个整数，即方案数。

思路

先将每一种数的个数打出来 a[i] 表示第i种数的数量 f[i,j] 表示前i种物品取j个的方案数，则状态转移方程为 f[i,j]=sum(f[i−1,j−k])k=0..a[i]

#include 
using namespace std;
int a[1000],f[1000][1000],b[1000];
int n,m,x,t;

int xx()
{
    int i,j;
    for (i=1;i<=n;i++)
    {
        if (b[i]==0)
        {
            b[i]=x;
            t++;
            a[i]++;
            return 0;
        }
        if (x==b[i])
        {
            a[i]++;
            return 0;
        }
    }
}
int main()
{
    freopen("Comb.in","r", stdin);
    freopen("Comb.out","w", stdout);
    t=0;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        xx();
    }

    for (int i=0;i<=n;i++)
        f[i][0]=1;
    for (int i=1;i<=t;i++)
        for (int j=1;j<=m;j++)
        {
            for (int k=0;k<=a[i];k++)
                if (j>=k)
                    f[i][j]=f[i-1][j-k]+f[i][j];
        }
    printf("%d",f[t][m]);
    return 0;
}