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，这玩意常数太大）

代码

#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;
}