题意：给出一个长度为 的正整数序列\(C_i\)，求一个子序列，使得原序列中任意长度为\(m\)的子串中被选出的元素不超过\(k(k,m\le 100)\) 个，并且选出的元素之和最大。
考虑DP。。发现没法合理定义状态，放弃。。
不过DP倒是可以做\(k=1\)的情况。我们把\(k>1\)的情况分割成\(k\)个子问题，每个子问题为：求一个子序列，使得原序列中任意长度为\(m\)的子串中被选出的元素不超过\(1\)个，并且选出的元素之和最大。
那么\(k\)个不相交的子问题的解就是原问题的解（具体证明不太会，想了想发现好像是对的。。）
然后“构造带权网络G=(V,A,C) 序列中的每个元素i用顶点i与i’表示，i→i’连边，容量为1，费用为该元素的数值value[i]，图中包含源S与汇T。 所有点i向点(i+1)连边，容量为+∞ ，费用为0。源S向所有点i各连一条边，容量为+∞，费用为0。所有点i’向汇T各连一条边，容量为+∞，费用为0。所有点i’向点(i+M)连边，容量为+∞ ，费用为0”（以上文字来源于论文）
从\(S\)到\(T\)跑\(k\)次SPFA求最大费用最大流，就是答案啦！
这样建图就是选了一个点之后强制从\(m\)个点之后的点开始寻找。。保证每长度为\(m\)的子串中最多只有一个元素。
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
const int INF = ~0U >> 2;
const int MAXN = 1000 * 2 + 5;
using std::max;
using std::min;
using std::vector;
using std::queue;
using std::priority_queue;
using std::fill;
typedef vector<int>::iterator vit;
struct MCMF {
struct Edge {
int from, to, cap, flow, cost;
Edge(int from, int to, int cap, int flow, int cost):
from(from), to(to), cap(cap), flow(flow), cost(cost) {}
};
int n, m, s, t;
vector<Edge> edges;
vector<int> G[MAXN];
bool inq[MAXN];
int d[MAXN], p[MAXN], a[MAXN];
inline void add_edge(int from, int to, int cap, int cost) {
edges.push_back(Edge(from, to, cap, 0, cost));
edges.push_back(Edge(to, from, 0, 0, -cost));
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool spfa(int& flow, int& cost) {
queue<int> que;
fill(d, d + n, -1);
fill(inq, inq + n, 0);
que.push(s);
d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF;
while (!que.empty()) {
int u = que.front(); que.pop();
inq[u] = false;
for (vit i = G[u].begin(); i != G[u].end(); ++i) {
Edge& e = edges[*i];
if (e.cap > e.flow && d[e.to] < d[u] + e.cost) {
d[e.to] = d[u] + e.cost;
p[e.to] = *i;
a[e.to] = min(a[u], e.cap - e.flow);
if(!inq[e.to]) que.push(e.to), inq[e.to] = true;
}
}
}
if (d[t] == -1) return false;
flow += a[t];
cost += a[t] * d[t];
int u = t;
while (u != s) {
edges[p[u]].flow += a[t];
edges[p[u] ^ 1].flow -= a[t];
u = edges[p[u]].from;
}
return true;
}
int maxcost(int _s, int _t, int k) {
s = _s; t = _t;
int flow = 0, cost = 0;
for (int i = 0; i < k; ++i) spfa(flow, cost);
return cost;
}
void init(int _n) {
n = _n;
edges.clear();
for (int i = 0; i < n; ++i) G[i].clear();
}
}S;
int n, m, k;
int a[MAXN >> 1];
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
int s = 0, t = 2 * n + 1;
S.init(2 * n + 2);
for (int i = 1; i <= n; ++i) S.add_edge(s, i, INF, 0);
for (int i = 1; i < n; ++i) S.add_edge(i, i + 1, INF, 0);
for (int i = 1; i <= n; ++i) S.add_edge(i, i + n, 1, a[i]);
for (int i = 1; i + m <= n; ++i)
S.add_edge(i + n, i + m, INF, 0);
for (int i = 1; i <= n; ++i)
S.add_edge(i + n, t, INF, 0);
printf("%d\n", S.maxcost(s, t, k));
}