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

· · 题解

这题还行吧，就难度而言emmm，其实这题首先用到了笛卡尔坐标系求斜率，看看是不是一条线上的（上过初中的都知道），然后呢在下面的金子肯定是被后挖到的，那么挖这块金子的前提，就是必须得把上面的都挖完，那么很明显这就是一个依赖性的背包问题了，相关题目详见noip2006金明的预算方案。。。。emmm，直接上代码吧

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct edge{
    int x,y,t,v;
    double b;
}e[2005];
bool cmp(edge x,edge y){
    if(x.b==y.b) return x.y<y.y;
    return x.b<y.b;
}
int n,T,cnt,js[2005];int v[2005][2005],t[2005][2005],f[40005];
int main(){
    memset(js,0,sizeof(js));
    scanf("%d%d",&n,&T);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].t,&e[i].v);
        e[i].b=e[i].y*1.0/(e[i].x*1.0);
    }
    sort(e+1,e+1+n,cmp);
    for(int i=1;i<=n;i++){
        if(e[i].b!=e[i-1].b||i==1)
            ++cnt;
        if(js[cnt]==0){
            v[cnt][++js[cnt]]=e[i].v;
            t[cnt][js[cnt]]=e[i].t;
        }
        else{
            ++js[cnt];
            v[cnt][js[cnt]]=v[cnt][js[cnt]-1]+e[i].v,t[cnt][js[cnt]]=t[cnt][js[cnt]-1]+e[i].t;
        } 
    }
    for(int i=1;i<=cnt;i++)
        for(int j=T;j>=t[i][1];j--){
            int maxn=f[j];
            for(int k=1;k<=js[i];k++){
                if(j>=t[i][k])
                    maxn=max(maxn,f[j-t[i][k]]+v[i][k]);
            }
            f[j]=maxn;
        }
    //for(int i=1;i<=cnt;i++)
    //  for(int j=1;j<=js[i];j++)
    //      printf("%d %d %d %d \n",i,j,t[i][j],v[i][j]);
    printf("%d",f[T]);
    return 0;
}

求审核大大给过，毕竟暂时只有我这么一篇题解

哪里不理解可以问我

距离NOIp2018还有99天，共勉！