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

· · 题解

P3961 [TJOI2013]黄金矿工

这其实是一道我们的考试题。。。（出题人竟然考原题太无耻了！）

反正我在考场上花了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，所以直接暴力。。。

还有的细节可以看看代码。

附代码：

#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;
}