查看Sgu/531的源代码 ←Sgu/531


[[分类:序列动态规划]]
==摘要==
{{信息题|Bonnie and Clyde|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}531|2|100|边界条件|2|time=2015-2-21 20:28:56}}
（AC 456）
==题意==
给出数轴上若干点的坐标<m>x_i</m>和价值<m>w_i</m>，求坐标相差≥d的两点之和的最大值。
==题解==
*算是个简单的DP，先排个序，然后按照方程进行转移：
::::Ans=<m>max\{P_j+w_i\}</m>(<m>x_i-x_j\geq d</m>,<m>P_j</m>表示坐标前j个点中价值最大值)
==代码==
{{折叠|531.cpp代码已折叠
|<pre>
#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;
}
</pre>
|sgu531}}