题解 P3961 【[TJOI2013]黄金矿工】
斯德哥尔摩
2018-10-03 22:55:45
[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;
}
```