BZOJ 1283 序列 题解

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

 

发表评论

电子邮件地址不会被公开。