atcoder.Camels and Bridge

链接：https://atcoder.jp/contests/arc105/tasks/arc105_c?lang=en
好题，一直打算写题解，鸽了好久。
首先N<8,8!=40320,dfs暴力枚举全排列。
然后看这个顺序过桥的从头到尾的最短距离是多少，我一开始构造的dp方程不对
dp[i]=min(dp[j]+max_len(j, i)),后来经过提醒意识到这个不对
重新写了一个方程:
dp[i]=max(dp[j]+min_len(j,i))
min_len可以二分去找到
这个dp转移方程确实值得好好想想
这题在二分上需要注意单调性的建立。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5+7;
struct Node{
    int l, v;
}b[maxn];
int n, m, w[10], dp[10], ans = 2e18;
bool vis[10];
int s[10];
int sum[10];

bool cmp(Node n1, Node n2){
    if(n1.l == n2.l) {
        return n1.v < n2.v;
    }
    else {
        return n1.l < n2.l;
    }
}


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

void work()
{
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; i++){
        sum[i] = sum[i-1] + w[s[i]];
    }
    for(int i = 2; i <= n; i++) {
        for(int j = i - 1; j >= 1; j--) {
            dp[i] = max(dp[i], dp[j] + erfen(sum[i]-sum[j-1]));
        }
    }
    ans = min(ans, dp[n]);
}


void dfs(int now)
{
    if(now == n+1){
        work(); return ;
    }
    for(int i = 1; i <= n; i++) {
        if(!vis[i]){
            vis[i] = 1;
            s[now] = i;
            dfs(now+1);
            vis[i] = 0;
        }
    }
}

signed main()
{
    memset(vis, 0, sizeof(vis));
    cin >> n >> m;
    int mw = 0;
    for(int i = 1; i <= n; i++) {
        cin >> w[i];
        mw = max(mw, w[i]);
    }
    for(int i = 1; i <= m; i++) {
        cin >> b[i].l >> b[i].v;
    }
    sort(b+1, b+m+1, cmp);
    int mx = 1e9;
    for(int i = m; i >= 1; i--) {
        mx = min(mx, b[i].v);
        b[i].v = mx;
    }
    b[0].v = mx; b[0].l = 0;
    if(mw > mx) {
        cout << -1 << endl;
        return 0;
    }

    dfs(1);
    cout << ans << endl;

    return 0;
}