解题思路

本题要求计算从给定的$n$个物体中选取$r$个物体时不同组合的数量。

1. 数据初始化与输入处理：
   • 定义数组num[51]记录每个标签物体的数量，dp[51][51]用于存储动态规划的中间结果。
   • 读取输入的$n$和$m$，以及$n$个物体的标签，同时记录物体标签的最大值Max和最小值Min。
   • 用memset函数将num和dp数组初始化为0 。
2. 动态规划初始化：
   • 对于标签为Min的物体，其数量为cnt。先将dp[Min][0]初始化为1，表示不选物体时有一种方案。
   • 然后将dp[Min][1]到dp[Min][cnt]都初始化为1，因为对于只有一种标签的物体，选取不同数量的方案数都是1 。
3. 动态规划递推：
   • 从标签Min + 1到Max进行遍历。对于每个标签i，先将dp[i][0]设为1，表示不选物体的方案数为1 。
   • 随着遍历，cnt累加当前标签物体的数量num[i] 。对于每个数量j（从1到cnt ），dp[i][j]的计算分两部分：
     • 一部分是不选当前标签i的物体，即dp[i - 1][j] 。
     • 另一部分是选择当前标签i的物体，通过枚举选择当前标签物体的数量k（从1到num[i] ），累加dp[i - 1][j - k] 。
4. 结果输出：
   • 读取每个测试用例中的$m$个$r$值。
   • 对于每个$r$，输出dp[Max][r]，即从所有物体中选取$r$个物体的不同组合数量。

#include<iostream>
using namespace std;
#include<cstring>

int n,m,r,num[51];
unsigned long long dp[51][51];

int main(){
    int nc = 1;
    while(cin>>n>>m&&(n||m)){
                             cout << "Case " << nc++ << ":" << endl;
                             int Max = -1, Min = 100;
                             memset(num,0,sizeof(num));
                             memset(dp,0,sizeof(dp));
                             for(int i = 0; i < n; i++){
                                     int t;
                                     cin >> t;
                                     num[t]++;
                                     Max = max(t,Max);
                                     Min = min(t,Min);
                             }
                             
                             int cnt = num[Min];
                             dp[Min][0] = 1;
                             for(int i = 1; i <= cnt; i++)
                                     dp[Min][i] = 1;
                             for(int i = Min+1; i <= Max; i++){
                                     dp[i][0] = 1;
                                     cnt+=num[i];
                                     for(int j = 1; j <= cnt; j++){
                                             dp[i][j] += dp[i-1][j];
                                             for(int k = 1; k <= num[i]; k++)
                                                     dp[i][j] += dp[i-1][j-k];
                                     }
                             }
                             
                             for(int i = 0; i < m; i++){
                                     cin >> r;
                                     cout << dp[Max][r] << endl;
                             }
    }
}