NC20699. 路灯孤影
描述
输入描述
第一行，一个整数n
接下来n行，每行一个整数l，r，表示路灯在l的位置上，且路灯最多能照亮r的长度
输出描述
一个整数，表示最大的没有黑暗的长度
示例1
输入:
3 1 1 2 2 3 3
输出:
5
说明:
所有的路灯都向右为最佳方案C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 484K, 提交时间: 2018-10-20 22:57:12
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std;
const int N=10010;
struct node{ int p,l,r; }a[N];
int n,cnt,b[N],id[N];
ll f[2][N];
inline bool cmp(node a,node b){return a.p<b.p;}
int main(){
scanf("%d",&n);
rep(i,1,n){
scanf("%d%d",&a[i].p,&a[i].l);
a[i].r=a[i].l;
b[++cnt]=a[i].p;
b[++cnt]=a[i].l=a[i].p-a[i].l;
b[++cnt]=a[i].r=a[i].p+a[i].r;
}
sort(b+1,b+cnt+1);
cnt=unique(b+1,b+cnt+1)-b-1;
sort(a+1,a+n+1,cmp);
rep(i,1,n){
a[i].p=lower_bound(b+1,b+cnt+1,a[i].p)-b;
a[i].l=lower_bound(b+1,b+cnt+1,a[i].l)-b;
a[i].r=lower_bound(b+1,b+cnt+1,a[i].r)-b;
id[a[i].p]=i;
}
rep(i,1,n){
rep(j,1,cnt) f[i&1][j]=f[(i-1)&1][j];
rep(j,a[i].l+1,a[i].p) f[i&1][j]=max(f[i&1][j],f[i&1][j-1]+b[j]-b[j-1]);
ll tmp=f[(i-1)&1][a[i].p];
rep(j,a[i].p+1,a[i].r){
f[i&1][j]=max(f[i&1][j],tmp+b[j]-b[a[i].p]);
if(id[j]&&a[id[j]].l<a[i].p)tmp=max(tmp,f[(i-1)&1][a[id[j]].l]+b[a[i].p]-b[a[id[j]].l]);
}
rep(j,2,cnt) f[i&1][j]=max(f[i&1][j],f[i&1][j-1]);
}
printf("%lld\n",f[n&1][cnt]);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 492K, 提交时间: 2018-10-20 19:50:16
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std;
const int N=10010;
struct node{ int p,l,r; }a[N];
int n,cnt,b[N],id[N];
ll f[2][N];
inline bool cmp(node a,node b){return a.p<b.p;}
int main(){
scanf("%d",&n);
rep(i,1,n){
scanf("%d%d",&a[i].p,&a[i].l);
a[i].r=a[i].l;
b[++cnt]=a[i].p;
b[++cnt]=a[i].l=a[i].p-a[i].l;
b[++cnt]=a[i].r=a[i].p+a[i].r;
}
sort(b+1,b+cnt+1);
cnt=unique(b+1,b+cnt+1)-b-1;
sort(a+1,a+n+1,cmp);
rep(i,1,n){
a[i].p=lower_bound(b+1,b+cnt+1,a[i].p)-b;
a[i].l=lower_bound(b+1,b+cnt+1,a[i].l)-b;
a[i].r=lower_bound(b+1,b+cnt+1,a[i].r)-b;
id[a[i].p]=i;
}
rep(i,1,n){
rep(j,1,cnt) f[i&1][j]=f[(i-1)&1][j];
rep(j,a[i].l+1,a[i].p) f[i&1][j]=max(f[i&1][j],f[i&1][j-1]+b[j]-b[j-1]);
ll tmp=f[(i-1)&1][a[i].p];
rep(j,a[i].p+1,a[i].r){
f[i&1][j]=max(f[i&1][j],tmp+b[j]-b[a[i].p]);
if(id[j]&&a[id[j]].l<a[i].p)tmp=max(tmp,f[(i-1)&1][a[id[j]].l]+b[a[i].p]-b[a[id[j]].l]);
}
rep(j,2,cnt) f[i&1][j]=max(f[i&1][j],f[i&1][j-1]);
}
printf("%lld\n",f[n&1][cnt]);
return 0;
}
C++(g++ 7.5.0)(g++7.5.0) 解法, 执行用时: 3ms, 内存消耗: 456K, 提交时间: 2023-02-20 19:31:50
#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
int x,d;
bool operator < (const node &ts){
return x<ts.x;
}
}a[105];
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].d;
}
int ans=0;
for(int i=1;i<=n;i++){
int r=a[i].x;
int l=a[i].x-a[i].d;
int j=i-1;
for(;j>=1;j--){
if(a[j].x>=l){
l=min(l,a[j].x-a[j].d);
}
}
j=i-1;
for(;j>=1;j--){
if(a[j].x+a[j].d>=l){
l=min(l,a[j].x);
r=max(r,a[j].x+a[j].d);
}
}
ans=max(ans,r-l);
}
for(int i=1;i<=n;i++){
int l=a[i].x;
int r=a[i].x+a[i].d;
int j=i+1;
for(;j<=n;j++){
if(a[j].x<=r){
r=max(r,a[j].x+a[j].d);
}
}
j=i+1;
for(;j<=n;j++){
if(a[j].x-a[j].d<=r){
l=min(l,a[j].x-a[j].d);
r=max(r,a[j].x);
}
}
ans=max(ans,r-l);
}
cout<<ans<<endl;
return 0;
}