这题也是拖欠了几天的...emmm
题目大意:你有n头骆驼,他们要过桥,桥呢,有m座有两个属性l,v,l是它的长度,v表示在这个长度下,你不能超过v的载重,你呢,必须.让你安排下他们的过桥顺序.假如它们能够过桥,就要算出你安排的第一头骆驼和最后一头骆驼的间距,否则的话,输出-1.
思路是这样滴.先判断下无解的情况哈.假如说你的骆驼的体重的max>桥载重的min,那么以必然无解输出-1,有解的情况呢?注意到n的大小只有8,那么我们不妨全排列一下.(果然思路不是自己的写完就可能忘了...我又忘了...emmm所以划水不划水都那样哈哈哈).
我们按长度进行一个排序,然后统计下长度排序完后载重的最小值,我们把骆驼进行分堆,每一堆都有一个限制条件(质量在这个的情况下最少需要多少长度.)每个都有一个限制条件,且当限制条件都满足时才行,都满足就是max的情况,随便dp下即可,我们对于每种骆驼的排序取个min即可.
#include <bits/stdc++.h> const int N=10,M=1e5+5; int w[N],n,m,suf[M],vis[N],ans=2e9,sum[N][N]; int dis[N][N];//表示限制下的最少长度. int f[N]; struct vv{ int l,v; }c[M]; bool cmp(vv a,vv b) { if(a.l==b.l) return a.v<b.v; else return a.l<b.l; }//按l排序. void solve() { for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { dis[i][j]=c[std::lower_bound(suf+1,suf+1+m,sum[i][j])-suf-1].l; } } for(int i=1;i<=n;i++) f[i]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=i-1;j++) { f[i]=std::max(f[j]+dis[j][i],f[i]); } } ans=std::min(ans,f[n]); } void dfs(int u) { if(u==n+1) { for(int i=2;i<=n;i++) { for(int j=1;j<=i-1;j++) { sum[j][i]=sum[j][i-1]+sum[i][i]; } } solve(); } for(int i=1;i<=n;i++) { if(vis[i]) continue; vis[i]=1;sum[u][u]=w[i];dfs(u+1); vis[i]=0; } } int main() { int mx=0,mi=2e9; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) {scanf("%d",&w[i]);mx=std::max(mx,w[i]);} for(int i=1;i<=m;i++) {scanf("%d%d",&c[i].l,&c[i].v);mi=std::min(mi,c[i].v);} if(mx>mi) { puts("-1");return 0; } std::sort(c+1,c+1+m,cmp);//按长度排序. suf[m]=c[m].v; for(int i=m-1;i>=1;i--) suf[i]=std::min(suf[i+1],c[i].v);//记录下后面载重的min dfs(1); printf("%d\n",ans); return 0; }