洛谷 P5194 [USACO05DEC] Scales S 刷题笔记

P5194 [USACO05DEC] Scales S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路参考 大佬?薛定谔的鱼 的个人中心 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

维护一个前缀和数组 从后往前一个个遍历所有可能的组合?

然后进行一定的剪枝

void bfs(int now,ll ma){
?? ?if(ma>m){
?? ??? ?return ;//不符合条件返回 #减枝1?
?? ?}
?? ?if(ma+b[now]<=ans){
?? ??? ?return ;//如果往前所有砝码全选上都小于当前最优答案 那么返回 #减枝2?
?? ?}
?? ?ans=max(ans,ma); //走到这已经符合条件 先判断更新一下答案 ?
?? ?for(int i=now;i;i--){
?? ??? ?bfs(i-1,ma+a[i]);//对于当前 now这个编号的砝码遍历其所有可能的组合?
?? ?}
}

遍历递归? 的逻辑图?

我们会一个个往前搜 搜完所有可能的组合

完整代码

#include<iostream>
using namespace std;
typedef long long ll;
ll ans;
int n,m;
ll a[1010],b[1010];
void bfs(int now,ll ma){
?? ?if(ma>m){
?? ??? ?return ;//不符合条件返回 #减枝1?
?? ?}
?? ?if(ma+b[now]<=ans){
?? ??? ?return ;//如果往前所有砝码全选上都小于当前最优答案 那么返回 #减枝2?
?? ?}
?? ?ans=max(ans,ma); //走到这已经符合条件 先判断更新一下答案 ?
?? ?for(int i=now;i;i--){
?? ??? ?bfs(i-1,ma+a[i]);//对于当前 now这个编号的砝码遍历其所有可能的组合?
?? ?}
}

int main(){
?? ?cin>>n>>m;
?? ?for(int i=1;i<=n;i++){
?? ??? ?cin>>a[i];
?? ??? ?b[i]=b[i-1]+a[i];
?? ?}
?? ?bfs(n,0);
?? ?cout<<ans;
?? ?
?? ?
?? ?return 0;
}