Camels and Bridge[ARC105C][二分+Dp]

题目

Atcoder
有 $n$ 只骆驼，第 $i$ 只重量为 $w_i$ 现在通过 $m$ 座桥，每个桥长度为 $l_i$,承重为 $v_i$ （允许骆驼踩在端点 $0$ 和 $l_i$ ），安排骆驼顺序使得队列长度最小
$n\le 8,m\le 10^5$

思路

首先排列枚举骆驼过桥顺序，然后 $dp$ 检验
$f_i$ ：前 $i$ 只骆驼过桥最短长度
$f_1=0$

然后有

$f_i=max(f_j+len(j,i))$

考虑为什么合理

然后考虑如何快速求出 $len$ ，判断一段骆驼最短长度
可以发现路长承重对路短的有限制
然后路按长度升序，承重也升序了
找到最长的无法承重的桥的长度就是这段骆驼的承重
确实比它短的可能也过不去

但就不是这段骆驼的问题了

代码

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<climits>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define int LL
int read(){
    int f=0,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define mp make_pair
const int MAXN=100000;
const int INF=1000000000000000000ll;
pair<int,int> c[MAXN+5];
int n,m,w[10],p[10],f[10],s[10];
int cal(int x){
    int L=0,R=m+1;while(L+1<R){
    int Mid=(L+R)>>1;if(c[Mid].second<x)L=Mid;else R=Mid;}return c[L].first;
}
signed main(){
    n=read(),m=read();for(int i=1;i<=n;i++)w[i]=read(),p[i]=i;for(int i=1;i<=m;i++)c[i].first=read(),c[i].second=read();//l_i,v_isort(c+1,c+m+1);int Min=INF;for(int i=m;i>=1;i--)Min=min(Min,c[i].second),c[i].second=Min;for(int i=1;i<=n;i++)if(Min<w[i]){
    puts("-1");return 0;}int ans=INF;do{
    memset(f,0,sizeof(f));for(int i=1;i<=n;i++)s[i]=s[i-1]+w[p[i]];for(int i=2;i<=n;i++)for(int j=1;j<=i-1;j++)f[i]=max(f[i],f[j]+cal(s[i]-s[j-1]));ans=min(ans,f[n]);}while(next_permutation(p+1,p+n+1));printf("%lld\n",ans);return 0;
}