Sgu/531

摘要

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

（AC 456）

题意

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

题解

• 算是个简单的DP，先排个序，然后按照方程进行转移：

Ans=(,表示坐标前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; }