P3040 [USACO12JAN]贝尔分享Bale Share

2019-11-04 21:11:57


题目描述

这是我们模拟赛题目……结果我这道题暴力50分……

FJ有N (N较小)包干草,干草i的重量是 $S_i$ ,他想尽可能平均地将干草分给3个农场。

他希望分配后的干草重量最大值尽可能地小。

思路简述

虽然这里有最大值最小,但是这道题并不需要二分答案,我们看到N只有20,于是希望枚举每个干草,但是我们发现: 图片.png

于是我们需要一些剪枝优化……

不妨设其中 $c\leq b\leq a$

  • 如果此时的 $a$ 的总和已经大于 $a$ 已算出的答案那么就不用算了
  • 如果此时 $a+x_i+x_{i+1}+……+x_n\leq b$ ,也就是a不可能再比b大了,就不用算了
  • 从大到小排序,有助于提早剪枝
  • 氧气(楼上的记忆化搜索开了好多map,这玩意常数太大)

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,x[25],ac=9999,ag=9999,af=9999,sum=0;
void dfs(ll p,ll c,ll g,ll f,ll ls){//dfs,ls表示剩余的数的总和
    if(c>=ac) return;//剪枝1
    if(f>c+ls||g>c+ls||f>g+ls) return;//剪枝2
    if(p==n+1){//搜索结束
        if(c<ac&&c>=g&&g>=f) ac=c,ag=g,af=f;
        return;
    }
    dfs(p+1,c+x[p],g,f,ls-x[p]);
    dfs(p+1,c,g+x[p],f,ls-x[p]);
    dfs(p+1,c,g,f+x[p],ls-x[p]);
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&x[i]),sum+=x[i];
    sort(x+1,x+n+1);
    reverse(x+1,x+n+1);//从大到小排序
    dfs(1,0,0,0,sum);//开始dfs
    printf("%lld",ac);//输出
    return 0;
}