题意简述

给定两个长度为 $n$ 的序列 $A$ 和 $B$，需要从 $n$ 个元素中选出恰好 $K$ 个，每个元素 $i$ 被选中的代价为 $A_i$，且若元素 $i$ 和 $j$（$i < j$）同时被选中，则额外增加 $B_j$ 的代价。求最小总代价。

思路分析

转化为网络流模型

观察代价结构：

• 选中元素 $i$ 本身付出 $A_i$
• 若选中 $i$ 且后面选中了 $j$（$i < j$），则付出 $B_j$（可以理解为每个 $j$ 对前面所有选中的 $i$ 各贡献一次 $B_j$，但注意题目通常搭配是“若 $i$ 选且 $j$ 选”只算一次？需要根据原题确认。从代码看，建图方式是每个 $i$ 向源点连 $A_i$，向伪汇点连 $B_i$，说明总代价 = $\sum A_i + \sum B_j$ 对所有选中的 $j$，且 $i<j$ 时也会重复算？实际上这是典型的“配对代价”网络流建模）

更常见的题意：选择恰好 $K$ 个元素，代价为 $\sum A_i + \sum_{j \text{选}} B_j \cdot (\text{前面选中的个数})$。这正是代码建图所对应的模型。

朴素建图

将每个元素拆成两个点（上点 $i$ 和下点 $i'$），源点 $S$ 连向 $i$（容量 1，费用 $A_i$），$i'$ 连向汇点 $T$（容量 1，费用 $B_i$），$i$ 向 $j'$（$i<j$）连边（容量 1，费用 0）。再限制总流量为 $K$。但这样边数为 $O(n^2)$，$n$ 可达 $2000$，无法接受。

优化建图：利用传递性

注意到 $i$ 向 $j'$ 连边 等价于 $i$ 先到一个中间点 $p_i$，$p_i$ 再到 $p_{i+1}$，...，最后到 $j'$。因此我们引入一排中间点 $1,2,\dots,n$：

• $i$ 向 $i$（中间点）连边（容量 1，费用 0）
• 中间点 $i$ 向 $i+1$ 连边（容量无穷，费用 0）
• 中间点 $i$ 向 $i'$ 连边（容量 1，费用 0）

这样，若 $i$ 被选中，流量可以从 $i$ 流入中间点链，然后从某个 $\ge i$ 的中间点 $j$ 流出到 $j'$，表示 $i$ 对 $j$ 产生了贡献。由于链上边容量无穷，多个前驱可以共享同一条路径到同一个 $j'$，但每个 $j'$ 只能接受 1 单位流量（因为连向 $T$ 的边容量 1），正好对应每个 $j$ 只会被计算一次 $B_j$。

费用流实现

• 源点 $S$ 连向每个 $i$（容量 1，费用 $A_i$）
• 每个 $i$ 连向中间点 $i$（容量 1，费用 0）
• 中间点 $i$ 连向 $i+1$（容量 $+\infty$，费用 0）
• 中间点 $i$ 连向伪汇点 $TT$（容量 1，费用 $B_i$）
• 伪汇点 $TT$ 连向真汇点 $T$（容量 $K$，费用 0）

跑最小费用最大流，最大流量为 $K$ 时的最小费用即为答案。

时间复杂度

• 点数 $O(n)$，边数 $O(n)$
• 每次 SPFA/SLF 优化后增广，实际运行效率很高，可处理 $n=2000$ 的数据。

AC 代码（含注释）

#include<bits/stdc++.h>
#define int long long
using namespace std;

int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return x * f;
}

const int INF = 1e15;
const int N = 5005, M = 100005;

int n, K, S, TT, T, cnt;
int a[N], b[N], d[N], head[N];
bool inq[N], vis[N];
deque<int> Q;

struct Edge {
    int to, cap, cost, next;
} e[M << 1];

void add(int u, int v, int w, int c) {
    e[cnt] = {v, w, c, head[u]}; head[u] = cnt++;
    e[cnt] = {u, 0, -c, head[v]}; head[v] = cnt++;
}

bool spfa() {
    for (int i = 0; i <= T; i++) d[i] = INF;
    memset(inq, 0, sizeof(inq));
    d[T] = 0; Q.push_back(T); inq[T] = true;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop_front(); inq[u] = false;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to;
            if (e[i ^ 1].cap && d[v] > d[u] - e[i].cost) {
                d[v] = d[u] - e[i].cost;
                if (!inq[v]) {
                    inq[v] = true;
                    if (Q.empty() || d[v] >= d[Q.front()]) Q.push_back(v);
                    else Q.push_front(v);
                }
            }
        }
    }
    return d[S] < INF;
}

int dfs(int u, int f) {
    vis[u] = true;
    if (u == T || f == 0) return f;
    int used = 0;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (!vis[v] && e[i].cap && d[v] == d[u] - e[i].cost) {
            int w = dfs(v, min(e[i].cap, f - used));
            e[i].cap -= w;
            e[i ^ 1].cap += w;
            used += w;
            if (used == f) return used;
        }
    }
    return used;
}

signed main() {
    n = read(), K = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) b[i] = read();

    S = n + 1, TT = n + 2, T = n + 3;
    memset(head, -1, sizeof(head));

    // 源点连向每个元素
    for (int i = 1; i <= n; i++) {
        add(S, i, 1, a[i]);           // 选中 i 的代价
    }

    // 中间点链
    for (int i = 1; i <= n; i++) {
        add(i, i, 1, 0);              // i 进入中间点链
        if (i != n) add(i, i + 1, INF, 0); // 链上传递
        add(i, TT, 1, b[i]);          // 从中间点流出到伪汇点，贡献 b[i]
    }

    // 伪汇点限制总流量为 K
    add(TT, T, K, 0);

    int flow = 0, cost = 0;
    while (spfa()) {
        memset(vis, 0, sizeof(vis));
        int f = dfs(S, INF);
        flow += f;
        cost += d[S] * f;
    }

    printf("%lld\n", cost);
    return 0;
}