1 条题解

  • 0
    @ 2025-5-7 11:58:34

    解题思路

    1. 输入与初步判断:读取Mindt巧克力数量m、Lilka巧克力数量l以及盒子数量n和每个盒子的容量a[i] 。计算所有盒子容量总和sum,若sum > m + l,说明巧克力总数不够装满所有盒子,直接输出 “Impossible to distribute” 并进入下一个测试用例。
    2. 动态规划初始化:使用布尔数组dp来记录能否用Mindt巧克力凑出对应重量,dp[j]表示能否用Mindt巧克力凑出重量为j ,初始化为全0 ,并设置dp[0] = 1 表示重量为0时可以凑出。同时,使用path数组记录每个重量是由哪个盒子的巧克力凑出的,初始化为-1
    3. 动态规划过程:对于每个盒子i,从当前能凑出的最大重量Max开始倒序遍历到0 。如果dp[j]true(即能凑出重量j )且dp[j + a[i]]false(即还不能凑出重量j + a[i] ),则更新dp[j + a[i]] = 1 ,并记录path[j + a[i]] = i 。更新MaxMax + a[i]m中的较小值,保证不超过Mindt巧克力的数量。
    4. 寻找合适的分配方案:从m开始递减寻找能凑出的最大重量p ,若sum - p > l,说明剩余巧克力超过了Lilka巧克力的数量,无法分配,输出 “Impossible to distribute” 并进入下一个测试用例。
    5. 构建并输出结果:若找到合适的p ,通过path数组反向追溯,将使用到的盒子编号存入res数组,最后按要求格式输出用Mindt巧克力装满的盒子数量和盒子编号。
    #include<iostream>
    using namespace std;
    #include <cstring>
    bool dp[2001];
    int a[2001], m,l,n, path[2001];
    
    int main(){
        while(cin >> m >> l&&(m||l)){
                  int sum = 0;
                  cin >> n;
                  for(int i = 0; i < n; i++){
                          cin >> a[i];
                          sum += a[i];
                  }
                  if(sum>m+l){
                              cout << "Impossible to distribute" << endl;
                              continue;
                  }
                  
                  memset(dp,0,sizeof(dp));
                  memset(path,-1,sizeof(path));
                  dp[0] = 1;
                  int Max = 0;
                  for(int i = 0; i < n; i++){
                          for(int j = Max; j >= 0; j--)
                                  if(dp[j]&&dp[j+a[i]]==0)
                                           dp[j+a[i]] = 1, path[j+a[i]] = i;
                          Max = min(Max+a[i],m);
                  }
                  
                  int p = m;
                  while(dp[p]==0) p--;
                  
                  if(sum-p>l){
                              cout << "Impossible to distribute" << endl;
                              continue;
                  }
                  
                  int res[1000],top = 0;
                  while(p>0){
                             res[top++] = path[p]+1;
                             p -= a[path[p]];
                  }
                  cout << top;
                  for(int i = top-1; i>=0; i--)
                          cout << " " << res[i];
                  cout << endl;
        }
    }
    • 1

    信息

    ID
    294
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    8
    已通过
    1
    上传者