题意：
一个长度为n的序列，要求从中挑k个不下降子序列出来（每个元素只能用一次），收益为这k个不下降子序列的和，问最大收益。
题解：
费用流。
我们先建一个源点s，然后把s拆为入点s0和出点s1，然后s0向s1连容量为k，费用为0的边。
然后对于每个数ai，拆为入点ai0和出点ai1，由ai0向ai1连容量为1，费用为-ai的边。
然后s1向每个ai0连容量为1，费用为0的边，每个ai1向t连容量为1，费用为0的边。
最后对于每对i<j，a[j]>=a[i]，由ai1向aj0连容量为1，费用为0的边。
最后对答案取反即可。
参考代码：
//by BigSheep 873ms
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4005;
const int inf = 0x3f3f3f3f;
int T, n, k;
int a[MAXN];
struct Edge
{
int v, w, c, rev;
//w流量 c费用
Edge(int v, int w, int c, int rev) : v(v), w(w), c(c), rev(rev){};
};
vector<Edge> edge[MAXN];
void addedge(int u, int v, int w, int c)
{
edge[u].push_back({Edge(v, w, c, edge[v].size())});
edge[v].push_back({Edge(u, 0, -c, edge[u].size() - 1)});
}
int flow, ans; //记录最大流和最小费用
int h[MAXN], dis[MAXN];
int pre_v[MAXN], pre_id[MAXN];
struct node
{
int u, d;
node(int u, int d) : u(u), d(d) {}
bool operator<(const node &a) const { return d > a.d; }
};
void MinCostFlow(int st, int ed, int Flow)
{
memset(h, 0, sizeof(h));
while (Flow > 0)
{
priority_queue<node> q;
while (!q.empty())
q.pop();
for (int i = 0; i <= n * 2 + 2; i++) //总点数
dis[i] = inf;
dis[st] = 0;
q.push({st, 0});
while (!q.empty())
{
int u = q.top().u;
int di = q.top().d;
q.pop();
if (di > dis[u])
continue;
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i].v, w = edge[u][i].w, c = edge[u][i].c;
if (w > 0 && dis[v] > dis[u] + c + h[u] - h[v])
{
dis[v] = dis[u] + c + h[u] - h[v];
pre_v[v] = u;
pre_id[v] = i;
q.push({v, dis[v]});
}
}
}
if (dis[ed] == inf)
break;
for (int i = 0; i <= n * 2 + 2; i++) //总点数
h[i] += dis[i];
int minflow = Flow;
for (int i = ed; i != st; i = pre_v[i])
minflow = min(minflow, edge[pre_v[i]][pre_id[i]].w);
Flow -= minflow;
flow += minflow;
ans += minflow * h[ed];
for (int i = ed; i != st; i = pre_v[i])
{
Edge &e = edge[pre_v[i]][pre_id[i]];
e.w -= minflow;
edge[i][e.rev].w += minflow;
}
}
}
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &k);
for (int i = 0; i <= 2 * n + 2; i++)
edge[i].clear();
addedge(0, 1, k, 0);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
int pos = i * 2;
addedge(1, pos, 1, 0);
addedge(pos, pos ^ 1, 1, -a[i]);
addedge(pos ^ 1, n * 2 + 2, 1, 0);
}
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (a[j] >= a[i])
{
int u = (i * 2) ^ 1, v = j * 2;
addedge(u, v, 1, 0);
}
ans = 0;
MinCostFlow(0, n * 2 + 2, inf);
printf("%d\n", -ans);
}
return 0;
}// by function2 343ms
#include <bits/stdc++.h>
#define MAXN 2000
#define MAXK 10
#define INF ((1 << 29) - 1)
using namespace std;
namespace Flow
{
const int N = 2 * MAXN + 2;
const int M = 2 * (MAXK + 4) * MAXN;
struct Edge
{
int u, v, res, cost, next;
Edge(int u = 0, int v = 0, int res = 0, int cost = 0, int next = 0) : u(u), v(v), res(res), cost(cost), next(next) {}
};
Edge edge[M + 10];
int head[N + 10], pp = 1;
void adde(int u, int v, int cap, int cost)
{
edge[++pp] = Edge(u, v, cap, cost, head[u]);
head[u] = pp;
edge[++pp] = Edge(v, u, 0, -cost, head[v]);
head[v] = pp;
}
int a[N + 10], p[N + 10], s, t, d[N + 10];
bool vis[N + 10];
bool spfa()
{
for (int i = s; i <= t; i++)
{
d[i] = -INF;
vis[i] = 0;
}
queue<int> que;
que.push(s);
d[s] = 0;
vis[s] = 1;
a[s] = INF;
while (!que.empty())
{
int u = que.front();
que.pop();
vis[u] = 0;
for (int i = head[u]; i; i = edge[i].next)
{
const Edge &e = edge[i];
if (e.res)
{
int v = e.v;
if (d[v] < d[u] + e.cost)
{
d[v] = d[u] + e.cost;
a[v] = min(a[u], e.res);
p[v] = i;
if (!vis[v])
{
que.push(v);
vis[v] = 1;
}
}
}
}
}
return d[t] != -INF;
}
int mfmc(int k)
{
int ret = 0;
while (k && spfa())
{
int cur = min(k, a[t]);
// printf("%d %d\n", a[t], d[t]);
ret += d[t] * cur;
for (int u, v = t; v != s; v = u)
{
int i = p[v];
u = edge[i].u;
edge[i].res -= cur;
edge[i ^ 1].res += cur;
}
k -= cur;
}
return ret;
}
void clear()
{
pp = 1;
for (int i = s; i <= t; i++)
head[i] = 0;
}
}; // namespace Flow
int a[MAXN + 10], num[MAXN + 10];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n, k;
scanf("%d%d", &n, &k);
using Flow::s;
using Flow::t;
s = 0;
t = 2 * n + 1;
for (int i = 1; i <= n; i++)
{
scanf("%d", a + i);
Flow::adde(s, i, 1, 0);
Flow::adde(i, i + n, 1, a[i]);
Flow::adde(i, i + n, INF, 0);
Flow::adde(i + n, t, 1, 0);
}
for (int i = 1; i <= n; i++)
{
for (int j = i + 1, cur = INF, cnt = 0; j <= n; j++)
{
if (a[i] <= a[j] && a[j] < cur)
{
cur = a[j];
cnt++;
Flow::adde(i + n, j, 1, 0);
}
}
}
printf("%d\n", Flow::mfmc(k));
Flow::clear();
}
return 0;
}