社区讨论
萌新WA一个点,求助
P9234[蓝桥杯 2023 省 A] 买瓜参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lt8p1z6o
- 此快照首次捕获于
- 2024/03/01 21:32 2 年前
- 此快照最后确认于
- 2024/03/02 01:11 2 年前
思路是dfs+剪枝
sum是前缀和,ans是答案,le是还剩下多少重量
两个剪枝:
①砍瓜次数大于等于已知最优剪枝
②剩余全部可选瓜重量之和(sum记录)超过所需重量剪枝
11号测试点WA,应输出4,程序输出6。
求指教
CPP#include<iostream>
#include<queue>
#include<algorithm>
#include<stdlib.h>
#include<time.h>
#define int long long
using namespace std;
int n, m, sum[100];
int a[100];
int ans = 31;
void dfs(int now, int le, int cnt) {
if (cnt >= ans || le > (sum[n] - sum[now - 1]))return;
if (le == 0) {
ans = cnt;
return;
}
for (int i = now; i <= n; i++) {
while (a[i] == a[i - 1])i++;
if (le >= a[i] / 2) {
dfs(i + 1, le - a[i] / 2, cnt + 1);
}
if (le >= a[i]) {
dfs(i + 1, le - a[i], cnt);
}
}
}
signed main() {
cin >> n >> m;
m = m * 2;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] *= 2;
}
sort(a + 1, a + n + 1);
reverse(a + 1, a + n + 1);
for (int i = 1; i <= n; i++)sum[i] = sum[i - 1] + a[i];
dfs(1, m, 0);
if (ans <= 30) {
cout << ans << endl;
}
else cout << -1 << endl;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...