1 条题解
-
0
解题思路
- 输入与初步判断:读取Mindt巧克力数量
m
、Lilka巧克力数量l
以及盒子数量n
和每个盒子的容量a[i]
。计算所有盒子容量总和sum
,若sum > m + l
,说明巧克力总数不够装满所有盒子,直接输出 “Impossible to distribute” 并进入下一个测试用例。 - 动态规划初始化:使用布尔数组
dp
来记录能否用Mindt巧克力凑出对应重量,dp[j]
表示能否用Mindt巧克力凑出重量为j
,初始化为全0
,并设置dp[0] = 1
表示重量为0
时可以凑出。同时,使用path
数组记录每个重量是由哪个盒子的巧克力凑出的,初始化为-1
。 - 动态规划过程:对于每个盒子
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
。更新Max
为Max + a[i]
和m
中的较小值,保证不超过Mindt巧克力的数量。 - 寻找合适的分配方案:从
m
开始递减寻找能凑出的最大重量p
,若sum - p > l
,说明剩余巧克力超过了Lilka巧克力的数量,无法分配,输出 “Impossible to distribute” 并进入下一个测试用例。 - 构建并输出结果:若找到合适的
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; } }
- 输入与初步判断:读取Mindt巧克力数量
- 1
信息
- ID
- 294
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 8
- 已通过
- 1
- 上传者