（以“ 分类:序列动态规划 ==摘要== {{信息题|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| | + | {{信息题|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个点中价值最大值) | |
| + | |||
==代码== | ==代码== | ||
{{折叠|531.cpp代码已折叠 | {{折叠|531.cpp代码已折叠 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| Bonnie and Clyde | ★☆☆☆☆ | 答案正确 | 100 | 2015-2-21 20:28:56 | 边界条件（2） |
（AC 456）
给出数轴上若干点的坐标和价值
，求坐标相差≥d的两点之和的最大值。
| 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;
}
|
CloudLunar