文章目录
题目思路代码
题目
Atcoder 有
n
n
n 只骆驼，第
i
i
i 只重量为
w
i
w_i
wi 现在通过
m
m
m 座桥，每个桥长度为
l
i
l_i
li,承重为
v
i
v_i
vi （允许骆驼踩在端点
0
0
0 和
l
i
l_i
li ），安排骆驼顺序使得队列长度最小
n
≤
8
,
m
≤
1
0
5
n\le 8,m\le10^5
n≤8,m≤105
思路
首先排列枚举骆驼过桥顺序，然后
d
p
dp
dp 检验
f
i
f_i
fi ：前
i
i
i 只骆驼过桥最短长度
f
1
=
0
f_1=0
f1=0
然后有
f
i
=
m
a
x
(
f
j
+
l
e
n
(
j
,
i
)
)
f_i=max(f_j+len(j,i))
fi=max(fj+len(j,i))
考虑为什么合理
然后考虑如何快速求出
l
e
n
len
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();
sort(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;
}
