摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
Bonnie and Clyde ★★☆☆☆ 答案正确 100 2015-2-21 20:28:56 边界条件(2)

(AC 456)

题意

给出数轴上若干点的坐标x_i和价值w_i,求坐标相差≥d的两点之和的最大值。

题解

  • 算是个简单的DP,先排个序,然后按照方程进行转移:
Ans=max\{P_j+w_i\}(x_i-x_j\geq d,P_j表示坐标前j个点中价值最大值)

代码

531.cpp代码已折叠
展开折叠内容
#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define si(n) scanf("%d",&n)
#define ci const int &
#define dsi(n) int n;si(n)
#define f(i,n) for(int i=1;i<=n;++i)
#define fi(i,p,n) for(int i=p;i<=n;++i)
#define fd(i,n) for(int i=n;i!=0;--i)
#define fdi(i,p,n) for(int i=n;i>=p;--i)
int countS[3]={},maxA=0,b=0;
class st
{
    public:
        int a,d,i,j;
        st():a(0),d(0),i(0),j(0){};
        st(ci _i,ci _j,ci _d):i(_i),j(_j),d(_d){};
        st(ci _i,ci _d):i(_i),d(_d){};
        friend bool operator <(const st&a,const st&b){return a.d<b.d;}
} p[200010]={},ans=st(-1,-1,-1),preMax[200010]={};
int main()
{
    dsi(n);
    dsi(D);
    int j=1;
    f(i,n)
    {
        si(p[i].d);
        si(p[i].a);
        p[i].i=i;
    }
    sort(p+1,p+n+1);
    p[0].d=1e+8;//fixed:边界条件//
    f(i,n)
    {
        preMax[i]=max(preMax[i-1],st(p[i].i,p[i].i,p[i].a));
        while(p[i].d-p[j].d>=D)++j;
        if(p[i].d-p[j-1].d>=D)
            --j,ans=max(ans,st(p[i].i,preMax[j].i,p[i].a+preMax[j].d));
    }
    printf("%d %d",ans.i,ans.j);
    return 0;
}

著作权声明[编辑]

关于[编辑]