Description

有3N個數，你需要選出一些數，首先保證任意長度為N的區間中選出的數的個數<=K個，其次要保證選出的數的個數最大。

Input

第一行兩個整數N，K。第二行有3N個整數。

Output

一行一個整數表示答案。

Sample Input

Sample Output

HINT

【數據范圍】N<=200，K<=10。

Source

By Sbullet

題解：單純形

這道題除了用單純形來做還可以寫網絡流哦!

除了區間的個數限制以外，還要加一個限制xi<=1，然后直接上板子就可以了。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstdio>#include<cmath>#define N 1003#define inf 1000000000#define eps 1e-7using namespace std;double b[N],c[N],a[N][N],ans,v;int n,k,m;void PRiov(int l,int e){	b[l]/=a[l][e];	for (int i=1;i<=n;i++)	 if (i!=e) a[l][i]/=a[l][e];	a[l][e]=1/a[l][e];	for (int i=1;i<=m;i++)	 if (fabs(a[i][e])>eps&&i!=l) {	 	b[i]-=b[l]*a[i][e];	 	for (int j=1;j<=n;j++)	 	 if (j!=e) a[i][j]-=a[i][e]*a[l][j];	 	a[i][e]=-a[i][e]*a[l][e];	 }	v+=c[e]*b[l];	for (int i=1;i<=n;i++)	 if (i!=e) c[i]-=c[e]*a[l][i];	c[e]=-c[e]*a[l][e];}double simple(){	int i,l,e;	double t;	while (true) {		for (i=1;i<=n;i++)         if (c[i]>eps) break;        e=i;        if (e==n+1) return v;        t=inf;        for (i=1;i<=m;i++)         if (a[i][e]>eps&&t>b[i]/a[i][e])          t=b[i]/a[i][e],l=i;        if (t==inf) return inf;        priov(l,e);	}}int main(){	freopen("a.in","r",stdin);	scanf("%d%d",&n,&k);	int n1=n; n*=3;	for (int i=1;i<=n;i++) scanf("%lf",&c[i]);	for (int i=1;i<=n-n1+1;i++) {		m++;		for (int j=i;j<=i+n1-1;j++)		 a[m][j]=1;		b[m]=k;	}	for (int i=1;i<=n;i++) {		m++;		a[m][i]=1; b[m]=1;	}	ans=simple();	printf("%.0lf/n",ans);}