【bzoj1283】序列线性规划与费用流

题目描述

给出一个长度为的正整数序列Ci，求一个子序列，使得原序列中任意长度为的子串中被选出的元素不超过K(K,M<=100) 个，并且选出的元素之和最大。

输入

第1行三个数N,m,k。接下来N行，每行一个字符串表示Ci。

输出

最大和。

样例输入

10 5 3
4 4 4 6 6 6 6 6 4 4

样例输出

题解

线性规划与费用流

关于线性规划与费用流的具体讲解参见 bzoj1061 。

这道题和那道差不多，都是给出一大堆限制条件，每个变量在限制条件中的出现是连续的。

所以我们可以按照那道题的思路来做。

原始限制条件是$\begin{cases}0\le x_i\le1\\x_1+x_2+...+x_m\le k\\x_2+x_3+...+x_{m+1}\le k\\...\\x_{n-m+1}+x_{n-m+2}+...+x_n\le k\end{cases}$，

转化为相等关系为$\begin{cases}0\le x_i\le1\\y_i\ge0\\x_1+x_2+...+x_m+y_1=k\\x_2+x_3+...+x_{m+1}+y_2=k\\...\\x_{n-m+1}+x_{n-m+2}+...+x_n+y_{n-m+1}=k\end{cases}$，

添加恒等关系0=0，上下差分并移项得$\begin{cases}x_1+x_2+...+x_m+y_1-k=0\\x_{m+1}-x_1+y_2-y_1=0\\x_{m+2}-x_2+y_3-y_2=0\\...\\x_{n-1}-x_{n-m-1}+y_{n-m}-y_{n-m-1}=0\\x_n-x_{n-m}+y_{n-m+1}-y_{n-m}=0\\-x_{n-m+1}-x_{n-m+2}-...-x_n-y_{n-m+1}+k=0\end{cases}$。

根据这个建图，将这n-m+2个限制条件看作点，那么S->1，容量为k，费用为0；n-m+2->T，容量为k，费用为0；i->i+1，容量为inf，费用为0；对于每个变量xi，判断它系数为+1的位置和系数为-1的位置，+1向-1连边。容量为1，费用为ci。

然后跑最大费用最大流出解，具体地，将费用取相反数，跑最小费用最大流，再反过来即可。

#include <cstdio>

#include <cstring>

#include <queue>

#define N 1500

#define M 30000

#define inf 0x3f3f3f3f

using namespace std;

queue<int> q;

int head[N] , to[M] , val[M] , cost[M] , next[M] , cnt = 1 , s , t , dis[N] , from[N] , pre[N];

void add(int x , int y , int v , int c)

{

	to[++cnt] = y , val[cnt] = v , cost[cnt] = c , next[cnt] = head[x] , head[x] = cnt;

	to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , next[cnt] = head[y] , head[y] = cnt;

}

bool spfa()

{

	int x , i;

	memset(from , -1 , sizeof(from));

	memset(dis , 0x3f , sizeof(dis));

	dis[s] = 0 , q.push(s);

	while(!q.empty())

	{

		x = q.front() , q.pop();

		for(i = head[x] ; i ; i = next[i])

			if(val[i] && dis[to[i]] > dis[x] + cost[i])

				dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i , q.push(to[i]);

	}

	return ~from[t];

}

int mincost()

{

	int ans = 0 , i , k;

	while(spfa())

	{

		k = inf;

		for(i = t ; i != s ; i = from[i]) k = min(k , val[pre[i]]);

		ans += k * dis[t];

		for(i = t ; i != s ; i = from[i]) val[pre[i]] -= k , val[pre[i] ^ 1] += k;

	}

	return ans;

}

int main()

{

	int n , m , k , i , x;

	scanf("%d%d%d" , &n , &m , &k) , s = 0 , t = n - m + 3;

	add(s , 1 , k , 0) , add(n - m + 2 , t , k , 0);

	for(i = 1 ; i <= n - m + 1 ; i ++ ) add(i , i + 1 , inf , 0);

	for(i = 1 ; i <= n ; i ++ )

	{

		scanf("%d" , &x);

		if(i <= m) add(1 , i + 1 , 1 , -x);

		else if(i > n - m) add(i - m + 1 , n - m + 2 , 1 , -x);

		else add(i - m + 1 , i + 1 , 1 , -x);

	}

	printf("%d\n" , -mincost());

	return 0;

}

巴特西

【bzoj1283】序列线性规划与费用流

最新文章

热门文章

巴特西

【bzoj1283】序列 线性规划与费用流

最新文章

热门文章

【bzoj1283】序列线性规划与费用流