题目描述 Description
现在有n个物品（有可能相同），请您编程计算从中取k个有多少种不同的取法。
输入描述 Input Description
输入文件有两行，第一行包含两个整数n,k(2<=n<=30,0<=k<=n)。第二行，包含n个整数表示物品的编号（范围1..1000）。编号相同的物品看作同一种物品。
输出描述 Output Description
输出仅一个整数，即方案数。
样例输入 Sample Input
5 2
1 2 3 4 5
样例输出 Sample Output
10
思路比较奇特
dp[i][j] 表示前i个物品里选了j个的方案数
转移的时候，枚举和第i个物品编号相同的物品选k个
dp[i][j]+=dp[p][j-k] p表示区间[p+1,i]内的物品编号相同
本题还可以背包求解
#include<cstdio>
#include<algorithm>
using namespace std;
int a[],dp[][];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
sort(a+,a+n+);
for(int i=;i<=n;i++) dp[i][]=;
for(int i=;i<=n;i++)
for(int j=;j<=min(i,m);j++)
{
int p=i;
for(;p && a[p]==a[i];p--);
for(int k=;k<=min(i-p,j);k++) dp[i][j]+=dp[p][j-k];
}
printf("%d",dp[n][m]);
}