这题也是拖欠了几天的...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;
}