题意:给出一个长度为 的正整数序列\(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)); }