题解 P3961 【[TJOI2013]黄金矿工】

斯德哥尔摩

2018-10-03 22:55:45

Solution

[P3961 [TJOI2013]黄金矿工](https://www.luogu.org/problemnew/show/P3961) 这其实是一道我们的考试题。。。~~(出题人竟然考原题太无耻了!)~~ 反正我在考场上花了$10min$把$T2$正解写完,再花$20min$把$T3$暴力写完,就开始写这个灰常坑的$T1$。。。 然后我发现当我把正解$YY$完,代码还没写完的时候,已经$2h30min$又过去了。。。 首先说一下思路: 我们发现这其实是个有限制条件的背包问题。 也就是说,如果$i,j$两个点到原点斜率相等,即:$\frac{y_i}{x_i}==\frac{y_j}{x_j}$,并且$|x_i|<|x_j|$,那么必须先取$i$,然后才可以选择取不取$j$;否则一定不能取$j$。 我的想法就是对于这些限制,建图。 从$x$最小的连到满足上述条件的最近的一个点,一直到最后一个点。 然后把所有的联通块$dfs$出来,每个联通块内都从第一个点到最后一个点做一次前缀和。 然后我们有了许多联通块,并且把有限制条件的背包转化成了分组背包,每组只能选一个物品。 这不就很好做了嘛。。。 但是那个建图很麻烦。。。 由于$n<=200$,所以直接暴力。。。 还有的细节可以看看代码。 附代码: ```cpp #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #define MAXN 210 #define MAXT 80010 #define eps (1e-15) using namespace std; int n,m; int t[MAXN],v[MAXN],dp[MAXT]; struct Point{//点 int x,y,t,v,id; }point[MAXN]; int c=1,top=0,head[MAXN],indegree[MAXN]; struct Edge{//图 int next,to; }a[MAXN*MAXN]; inline int read(){//读入优化 int date=0,w=1;char c=0; while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();} while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();} return date*w; } inline bool cmp1(const Point &p,const Point &q){//按横纵坐标排序 if(p.x==q.x)return p.y<q.y; return p.x<q.x; } inline bool cmp2(const Point &p,const Point &q){//按联通块编号排序 if(p.id==q.id)return abs(p.x)<abs(q.x);//记得有这句。。。 return p.id<q.id; } inline void add_edge(int x,int y){//连单向边 indegree[y]++;//入度,用于判断联通块的根 a[c].to=y;a[c].next=head[x];head[x]=c++; } inline double slope(double x,double y){//某点到原点的斜率 if(x==0)return 0.00; return (double)y/x; } void build(){//建图 //分成三段来考虑建图:y轴左侧,y轴上,y轴右侧 //这三段互不影响,可以画个图感性理解一下。。。 int boundary=1,last;//每一段的起止点 while(point[boundary].x<0)boundary++; for(int i=boundary-1;i>=1;i--)//暴力对y轴左侧建图,记得是倒着搜 for(int j=i-1;j>=1;j--){ if(i==j)return; if(fabs(slope(point[i].x,point[i].y)-slope(point[j].x,point[j].y))<eps){ point[j].v+=point[i].v;point[j].t+=point[i].t; add_edge(i,j); break;//只加最近的点 } } last=boundary; while(point[boundary].x==0)boundary++;//对y轴上的建图 for(int i=last+1;i<boundary;i++){point[i].v+=point[i-1].v;point[i].t+=point[i-1].t;} last=boundary; for(int i=last;i<=n;i++)//对y轴右侧的建图 for(int j=i+1;j<=n;j++){ if(i==j)return; if(fabs(slope(point[i].x,point[i].y)-slope(point[j].x,point[j].y))<eps){ point[j].v+=point[i].v;point[j].t+=point[i].t; add_edge(i,j); break;//同样只加最近的点 } } } void dfs(int rt){//dfs求联通块 for(int i=head[rt];i;i=a[i].next){ int will=a[i].to; point[will].id=point[rt].id;//直接把联通块的编号弄成相等 dfs(will); } } void work(){//开始dp for(int i=1;i<=n;i++){v[i]=point[i].v;t[i]=point[i].t;}//为了方便。。。 for(int i=1;i<=n;i++){ int l=i,r=i;//每个联通块的左右区间 while(point[r+1].id==point[l].id)r++;//直接搜 for(int k=m;k>=t[l];k--){//对每个容量大小dp一次 int s=dp[k]; /* 由于这个块内只能选一个,那么也就是说,只有一个最大值是我们要dp出来的 所以我们的滚动数组就不能边dp边滚动了 而是要最后滚动一次,中间过程用个变量记一下最大值就好 */ for(int j=l;j<=r;j++)if(k>=t[j])s=max(s,dp[k-t[j]]+v[j]); dp[k]=s;//最后滚动 } i=r;//记得直接跳。。。 } printf("%d\n",dp[m]);//输出 } void init(){//预处理 n=read();m=read(); for(int i=1;i<=n;i++){ point[i].x=read();point[i].y=read(); point[i].t=read();point[i].v=read(); } sort(point+1,point+n+1,cmp1);//先按横纵坐标排个序 build();//建图 for(int i=1;i<=n;i++)//求联通块 if(!indegree[i]){ point[i].id=i; dfs(i); } sort(point+1,point+n+1,cmp2);//把每个联通块弄到一段连续的序列中 } int main(){//主函数So easy! init(); work(); return 0; } ```