首页 > 代码库 > bzoj3822: 文学
bzoj3822: 文学
Description
巨酱和主席是一对好朋友。他们都很喜欢读书，经常一起阅读相关领域书籍，进行系统的学习。一天主席列出了一份列表，里面共 p 本书，其中不乏《约翰克里斯多夫》，《名人传》等名著。作为一名在文学上有很高修养的知名青年，巨酱打算用尽量少的时间把这份列表中的所有书籍都读完。
作为一名文化人，巨酱阅读书籍的方式也与一般人不同。他使用一种叫做“批量阅读”的阅读方式。首先他根据自己的喜好，对每本书给出了个参数 x,y，其中 i 本书的两个参数为 xi,yi。当然，由于巨酱独特的口味，可能有两本不同的书，它们的 x、y 参数均相同。而每次阅读的时候，他会设置三个系数 a, b, c，所有满足 ax+by≤c 的书籍都可以通过这次“批量阅读”读完，这次批量阅读总共需要 w 的时间。
现在，巨酱有 n 种 “批量阅读”的方案，第 i 种“批量阅读”三个参数为 ai,bi,ci，需要的时间为 wi。现在巨酱打算从这 n 种“批量阅读”中选出若干，使得巨酱可以用尽量少的时间读完所有的书。现在我们想知道，巨酱最少用多少时间？
Input
第一行两个正整数 n,p，分别表示“批量阅读”的方案数以及书的数量。
接下来 n 行，每行四个整数，其中第 i 行包含四个整数 ai,bi,ci,wi，表示第 i 种“批量阅读”的方案。
接下来 p 行，每行两个整数，其中第 i 行包含两个整数 xi,yi，表示第 i 本书的参数。
Output
一行一个整数，表示最少需要的时间。若无论如何也无法读完全部书籍，则输出 −1。
每本书看作平面上一点，每个方案则为一个半平面，转化为求最小权值和的 半平面并 覆盖所有点。
首先可以特判掉一个半平面覆盖所有点的情况，其余情况的解至少有两个半平面，那么可以枚举其中的两个半平面，以半平面的交点为中心对其余未被覆盖的点进行极角排序
可以发现存在一种划分贡献的方式，使排序后的点被划分为几个连续段，每段被解中的某个半平面覆盖，于是可以区间dp，总复杂度是O(n4)
在判定点在半平面内时，计算结果在1012内，且计算结果和原数值都为整数，用double可以精确表示和计算
#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>const int inf=0x3f3f3f3f;int n,m;struct hp{ double a,b,c;int v; void read(){scanf("%lf%lf%lf%d",&a,&b,&c,&v);}}h[103];struct pos{ double x,y; void read(){scanf("%lf%lf",&x,&y);} bool in(hp w){return x*w.a+y*w.b<=w.c;} pos operator-(pos w){return (pos){x-w.x,y-w.y};} double operator*(pos w){return x*w.y-y*w.x;}}p[103],s[103];pos p0;bool operator<(pos a,pos b){ return (a-p0)*(b-p0)<0;}pos cross(hp x,hp y){ double v=x.a*y.b-y.a*x.b; return (pos){(x.c*y.b-y.c*x.b)/v,(x.c*y.a-y.c*x.a)/-v};}int f[103],g[103][103],sp=0,ans=inf;void mins(int&a,int b){if(a>b)a=b;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i)h[i].read(); for(int i=1;i<=m;++i)p[i].read(); for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j)if(!p[j].in(h[i]))goto o; mins(ans,h[i].v);o:; } for(int i=1;i<=n;++i){ for(int j=1;j<i;++j){ sp=0; p0=cross(h[i],h[j]); for(int k=1;k<=m;++k)if(!(p[k].in(h[i])||p[k].in(h[j])))s[++sp]=p[k]; std::sort(s+1,s+sp+1); memset(f,0x3f,sizeof f); memset(g,0x3f,sizeof g); for(int a=1;a<=n;++a)if(a!=i&&a!=j){ for(int l=1,r;l<=sp;++l){ if(!s[l].in(h[a]))continue; for(r=l;r<sp&&s[r+1].in(h[a]);++r); mins(g[l][r],h[a].v); l=r+1; } } for(int d=sp;d>1;--d)for(int l=1,r=d;r<=sp;++l,++r)mins(g[l][r-1],g[l][r]),mins(g[l+1][r],g[l][r]); f[0]=0; for(int b=1;b<=sp;++b)for(int a=0;a<b;++a)mins(f[b],f[a]+g[a+1][b]); mins(ans,f[sp]+h[i].v+h[j].v); } } printf("%d",ans==inf?-1:ans); return 0;}
bzoj3822: 文学
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。