如果 这题 是用单纯形做的话，这题就没什么加强了…… 裸的线性规划。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const double eps=1e-8; double a[10005][1005]; int n,m,id[20005]; void Pivot(int l,int e){ swap(id[n+l],id[e]); double t=a[l][e]; a[l][e]=1; for(int i=0;i<=n;i++) a[l][i]/=t; for(int i=0;i<=m;i++) if(i!=l&&fabs(a[i][e])>eps){ t=a[i][e]; a[i][e]=0; for(int j=0;j<=n;j++) a[i][j]-=t*a[l][j]; } } bool Simplex(){ while(1){ int l=0,e=0; double _min=1e+50; for(int i=1;i<=n;i++) if(a[0][i]>eps){ e=i; break; } if(!e) break; for(int i=1;i<=m;i++) if(-a[i][e]<-eps&&a[i][0]/a[i][e]<_min) _min=a[i][0]/a[i][e], l=i; if(!l) return false; Pivot(l,e); } return true; } int main(){ freopen("bzoj3265.in","r",stdin); freopen("bzoj3265.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lf",&a[0][i]); for(int i=1;i<=m;i++){ int t,x,y; scanf("%d",&t); while(t--){ scanf("%d%d",&x,&y); for(int j=x;j<=y;j++) a[i][j]=1; } scanf("%lf",&a[i][0]); } for(int i=1;i<=n;i++) id[i]=i; Simplex(); printf("%d\n",(int)(-a[0][0]+0.5)); return 0; }