Camels and Bridge

链接：https://vjudge.net/contest/401586#problem/C
题意：
有n个骆驼过桥，骆驼的重量为w1,w2,...,wn，桥由M段连成，每段的长度为li,承重为wi,可以调整骆驼的先后顺序，问骆驼能通过桥首尾的最短距离为多少？
思路：
n很小，那么可以暴力出n的全排列。
令dp[i]表示从第1只骆驼到第n只骆驼能通过的最短距离。
转移方程：
dp[i]=max(dp[i],dp[j] + len(j, i)){len(j,i)为j到i的最短距离}
解释一下转移方程：
dp[j]是前j个能通过，那么不管它们，考虑j到i能通过的j到i的最短距离？
如何判断能通过的最短距离？那么就是从桥中找到最短的一节桥，且使得桥的承重大于等于j到i的总重量。这个可以通过二分去找。(二分要预处理桥的长度哟，这是因为选中一节桥作为距离，大于这个长度的在过桥中也要满足)dp[i]可以通过1到i-1的所有情况转移过来，实际上这些情况在过桥的过程中都会发生(或者说1-i的过桥都可以由这个转移方程来理解)，因此要取max。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = getchar();
    }
    res *= f;
}
const int maxn = 1e5+7;
struct Node{
    int l, v;
    bool operator < (const Node & n1) const{
        if(l == n1.l) {
            return v > n1.v;
        }
        else return l < n1.l;
    }
}a[maxn];
int n, m, res, b[10], w[10], s[10], dp[10];
bool vis[10];

//int bsearch(int x)
//{
//    int l = 1, r = m;
//    int res = 0;
//    while (l < r)
//    {
//        int mid = l + r  >> 1;
//        if (x > a[mid].v) {
//            res = a[mid].l;
//            l = mid;
//        }
//        else r = mid - 1;
//    }
//    return res;
//}


int find(int x) {
    int l = 1, r = m;
    int res = 0;
    while(l <= r) {
        int mid = l + r + 1>> 1;
        if(x > a[mid].v) {
            res = a[mid].l;
            l = mid + 1;
        } else r = mid - 1;
    }
    return res;
}

//dp[i] = max(dp[i], dp[j] + len)
void work()
{
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; i++) {
        s[i] = s[i-1] + w[b[i]];
    }
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j <= i-1; j++) {
            int tmp = s[i] - s[j-1];
            int len = bsearch(tmp);
            dp[i] = max(dp[i], dp[j] + len);
        }
    }
    res = min(res, dp[n]);
}

void dfs(int cnt) {
    if(cnt == n + 1) {
        work(); //这个work函数好方便，学到了 
        return ;
    }
    for(int i = 1; i <= n; i++) {
        if(vis[i]) continue;
        vis[i] = 1;
        b[cnt] = i;
        dfs(cnt + 1);
        vis[i] = 0;
    }
}

signed main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) read(w[i]);
    for(int i = 1; i <= m; i++) {
        read(a[i].l); read(a[i].v);
    }
    sort(a + 1, a + m + 1);
    int mi = INF;
    for(int i = m; i >= 1; i--) {
        mi = min(mi, a[i].v);
        a[i].v = mi;
    }
    for(int i = 1; i <= n; i++) {
        if(w[i] > mi) {
            cout << -1 << endl;
            return 0;
        }
    }
    res = INF;
    dfs(1);
    cout << res << '\n';
}