【ARC105C】Camels and Bridge 题解

题意

给定 \(n\) 只骆驼和每条骆驼的重量 \(a_i\)。
这些骆驼要通过一条路，这条路被分为 \(m\) 个部分，每个部分的长度为 \(l_i\)，限重为 \(v_i\)。同时经过这部分的骆驼的重量和不能超过限重，否则就会坍塌。
你可以指定这 \(n\) 只骆驼的顺序和两两之间的距离，问第一只骆驼和最后一只的最短距离。如果走不了，输出 \(-1\)。
\(n \leq 8,m \leq 10^5,l_i,r_i,v_i \leq 10^8\)。

Sol

看到 \(n\) 很小，考虑暴力一点的做法。
首先记一个 \(w_s\) 表示当前骆驼集合为 \(s\) 时需要隔开的距离。
然后暴力枚举骆驼的顺序，记 \(dp_i\) 表示前 \(i\) 只骆驼的最短距离。直接转移即可。
时间复杂度 \(O(n!n^2)\)。

Code

//LYC_music yyds!
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0)
#define lowbit(x) (x&(-x))
using namespace std;
inline char gc()
{
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
int read()
{
	int pos=1,num=0;
	char ch=getchar();
	while (!isdigit(ch))
	{
		if (ch=='-') pos=-1;
		ch=getchar();
	}
	while (isdigit(ch))
	{
		num=num*10+(int)(ch-'0');
		ch=getchar();
	}
	return pos*num;
}
void write(int x)
{
	if (x<0)
	{
		putchar('-');
		write(-x);
		return;
	}
	if (x>=10) write(x/10);
	putchar(x%10+'0');
}
void writesp(int x)
{
	write(x);
	putchar(' ');
}
void writeln(int x)
{
	write(x);
	putchar('\n');
}
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
uint32_t y=rnd();//normally y will in [0,2^32)
const int N=1e5+10;
int n,a[N],l[N],v[N],w[N],p[N],dp[N],ans,m;
signed main()
{
	n=read(); m=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=1;i<=m;i++) l[i]=read(),v[i]=read();
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (a[i]>v[j]) return puts("-1"),0;
	for (int S=1;S<(1<<n);S++)
	{
		int s=0;
		for (int i=1;i<=n;i++)
			if ((S>>(i-1))&1) s+=a[i];
		for (int i=1;i<=m;i++)
			if (s>v[i]) w[S]=max(w[S],l[i]);
	}
	for (int i=1;i<=n;i++) p[i]=i; ans=0x3f3f3f3f;
	do
	{
		dp[0]=0;
		for (int i=2;i<=n;i++)
		{
			int now=1<<(p[i]-1); dp[i]=0;
			for (int j=i-1;j;j--) now|=1<<(p[j]-1),dp[i]=max(dp[i],dp[j]+w[now]);
		}
		ans=min(ans,dp[n]);
	}while(next_permutation(p+1,p+n+1));
	writeln(ans);
}