[ARC105C] Camels and Bridge 题解

出自梦熊比赛后，梦熊比赛出原题了，忘周知。
也许更好的阅读体验

思路

全排列，差分约束，二分。

全排列

\(n \leq 8\) ，且要指定顺序，易想到用全排列枚举所有状态。

差分约束

在全排列之后，需要求得每种状态的最短距离。定义所有骆驼的编号的集合为 \(S\) ，所有路的部分的编号的集合为 \(E\)，定义数组 \(sum,dis\) , \(sum_i\) 表示 \(\sum_{j = 1}^ia_j\) , \(dis_i\) 表示从起点到点 \(i\) 的最短距离， 则对于每对 \(i, j(i,j \in S, i \lt j)\) ，应该有若 \(sum_j - sum_{i - 1} \geq v_k\) ,则 \(dis_j - dis_i \geq l_k(k \in E)\) 。 转换一下，即若\(sum_j - sum_{i - 1} \geq v_k\) ,则 \(dis_i + l_k \leq dis_j(k \in E)\) , 很明显的差分约束条件，跑差分约束就行。

二分

跑差分约束需要建边。
对每个路的部分按 \(v\) 从小到大排序，对于每个 \(dv = sum_j - sum_{i - 1}\), 二分最大的 \(v_k \lt dv\) , 此时用所有 \(i(1 \leq i \leq k)\) 建边等效与用最大的 \(l_i\) 建边。用前缀 max 可以 \(O(1)\) 的建边。

总时间复杂度为 \(O(n!n^2\log m + m\log m)\)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
typedef long long LL;

using namespace std;

const int N = 10, M = 1e5 + 5;

#define mid (l + r >> 1)
#define pu puts("====================");
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)

int temp[10] = {1, 2, 3, 4, 5, 6, 7, 8};
int head[N], nxt[N * N], ver[N * N];
struct node{ LL l, v; } rd[M];
LL a[N], Max, Min = 1e18;
LL PMax[M], ans = 1e18;
LL edge[N * N], sum[N];
int ind[N], n, m, ts = 1, tot = 1;
queue<LL> que;
LL dis[N];

void add(int u, int v, LL w) {
    ver[++tot] = v, edge[tot] = w;
    nxt[tot] = head[u], head[u] = tot;
}

void Init() {
    tot = 1;
    memset(dis, 0, sizeof(dis));
    memset(ind, 0, sizeof(ind));
    memset(head, 0, sizeof(head));
    memset(ver, 0, sizeof(ver));
    memset(nxt, 0, sizeof(nxt));
    memset(edge, 0, sizeof(edge));
}

bool cmp(node a, node b) { return a.v < b.v; }

void topo() {
    LF(i, 1, n) if (!ind[i]) que.push(i);
    
    while (que.size()) {
        LL u = que.front();
        que.pop();
        for (int i = head[u]; i; i = nxt[i]) {
            int v = ver[i]; LL w = edge[i];
            dis[v] = max(dis[v], dis[u] + w);
            ind[v]--;
            if (!ind[v]) que.push(v);
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    
    LF(i, 1, n) {
        scanf("%d", &a[i]);
        Max = max(a[i], Max);
    }

    LF(i, 1, m) {
        scanf("%d%d", &rd[i].l, &rd[i].v);
        Min = min(rd[i].v, Min);
    }

    if (Max > Min) { puts("-1"); return 0; }

    LF(i, 1, n) ts *= i;
    sort(rd + 1, rd + m + 1, cmp);
    LF(i, 1, m) { PMax[i] = max(PMax[i - 1], rd[i].l); }

    LF(i, 1, ts) {
        Init();
        LF(i, 1, n) sum[i] = sum[i - 1] + a[temp[i - 1]];

        LF(i, 1, n) LF(j, i + 1, n) {
            LL v = sum[j] - sum[i - 1];
            LL l = 1, r = m, c = -1;

		    while (l <= r) {
			    if (rd[mid].v < v) l = (c = mid) + 1;
			    else r = mid - 1;
		    }
		
		    if (c == -1) continue;
            add(i, j, PMax[c]);
            ind[j]++;
        }
        topo();
        ans = min(ans, dis[n]);
        next_permutation(temp, temp + n);
    }
    printf("%lld", ans);
    return 0;
}