(以“ 分类:序列动态规划 ==摘要== {{信息题|Bonnie and Clyde|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}531|2|100|边界条件|2|time=2015-2-2...”为内容创建页面)
 
题解: 排版
 
(未显示1个用户的1个中间版本)
第2行: 第2行:
 
[[分类:序列动态规划]]
 
[[分类:序列动态规划]]
 
==摘要==
 
==摘要==
{{信息题|Bonnie and Clyde|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}531|2|100|边界条件|2|time=2015-2-21 20:28:56}}
+
{{信息题|Bonnie and Clyde|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}531|1|100|边界条件|2|time=2015-2-21 20:28:56}}
 
(AC 456)
 
(AC 456)
 +
 
==题意==
 
==题意==
 
给出数轴上若干点的坐标<m>x_i</m>和价值<m>w_i</m>,求坐标相差≥d的两点之和的最大值。
 
给出数轴上若干点的坐标<m>x_i</m>和价值<m>w_i</m>,求坐标相差≥d的两点之和的最大值。
 
==题解==
 
==题解==
 
*算是个简单的DP,先排个序,然后按照方程进行转移:
 
*算是个简单的DP,先排个序,然后按照方程进行转移:
::::Ans=<m>max\{P_j+w_i\}</m>(<m>x_i-x_j\geq d</m>,<m>P_j</m>表示坐标前j个点中价值最大值)
+
::Ans=<m>max\{P_j+w_i\}</m>(<m>x_i-x_j\geq d</m>,<m>P_j</m>表示坐标前j个点中价值最大值)
 +
 
 
==代码==
 
==代码==
 
{{折叠|531.cpp代码已折叠
 
{{折叠|531.cpp代码已折叠

2015年2月21日 (六) 22:49的最后版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
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;
}

著作权声明[编辑]

关于[编辑]