P3040 [USACO12JAN]贝尔分享Bale Share

URL 洛谷

题目描述

这是我们模拟赛题目……结果我这道题暴力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,这玩意常数太大)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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;
}