3550: [ONTAK2010]Vacation
Time Limit: 10 Sec Memory Limit: 96 MB Submit: 310 Solved: 222 [Submit][Status][Discuss] Description
有3N个数，你需要选出一些数，首先保证任意长度为N的区间中选出的数的个数<=K个，其次要保证选出的数的个数最大。
Input
第一行两个整数N，K。 第二行有3N个整数。
Output
一行一个整数表示答案。
Sample Input
5 3
14 21 9 30 11 8 1 20 29 23 17 27 7 8 35
Sample Output
195
HINT
【数据范围】
N<=200，K<=10。
Source
By Sbullet
sol: 单纯形，注意一下这里要限制每个点只能选一次。
#include<cstdio> #include<algorithm> #include<string> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> using namespace std; int n,m,M; inline int read() { char c; int res,flag=0; while((c=getchar())>'9'||c<'0') if(c=='-')flag=1; res=c-'0'; while((c=getchar())>='0'&&c<='9') res=(res<<3)+(res<<1)+c-'0'; return flag?-res:res; } const int N=1110; const double eps=1e-8; int l,e; double a[N][N],b[N],c[N]; double v; inline void pivot() { b[l]/=a[l][e]; for(int i=1;i<=m;++i) if(i!=e) a[i][e]/=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<=m;++j) if(j!=e) a[i][j]-=a[l][j]*a[i][e]; a[i][e]*=-a[l][e]; } v+=c[e]*b[l]; for(int i=1;i<=m;++i) if(i!=e) c[i]-=c[e]*a[l][i]; c[e]*=-a[l][e]; } inline double simplex() { while(true) { l=0;e=0; for(e=1;e<=m;++e) if(c[e]>eps) break; if(e==m+1) return v; double save=1e9; for(int i=1;i<=M;++i) if(a[i][e]>eps&&save>b[i]/a[i][e]) save=b[i]/a[i][e],l=i; // if(save==1e9) return 1e9; pivot(); } } int main() { // freopen("3550.in","r",stdin); // freopen(".out","w",stdout); n=read(); m=n*3; int k=read(); for(int i=1;i<=m;++i) c[i]=read(); for(int i=n*2+1;i>=1;--i) { b[i]=k; for(int j=1;j<=n;++j) if(i+j-1>m) break; else a[i][i+j-1]=1; } M=n*2+1; for(int i=1;i<=m;++i) { ++M; b[M]=1; a[M][i]=1; } printf("%d",(int)(simplex()+0.5)); }