Fork me on GitHub

Codeforces559E

Codeforces559E题解

题意:

  • 一条路上有$n$盏不同的灯,每盏灯所在位置为$p_i$,向左或者向右可以照射的距离为$l_i$,求最大总照射长度。
  • $n \leq 100,l_i,p_i \leq 10^8$。

题解:

  • 这道题dp思路似乎都很神奇?
  • 设$dp[i][j][k]$表示到第$i$盏灯(按位置从左到右),最左边的需要覆盖到的位置是$j$(0代表不存在未覆盖),最右端位置是$k$,包括了这段实际没有覆盖的最大总长度。
  • 考虑转移:
    • 向右照射,且之前的最左边需要覆盖的位置不变,转移方程:
    • 向左照射,且覆盖掉了原来实际没有覆盖(或者原来没有未覆盖)的部分,转移方程:
    • 向右照射,且原来没有未覆盖部分,最右边位置在当前灯位置左边,取最右边位置后某一处$j$到当前位置作为假装覆盖实际没有覆盖部分(或者不选取),转移方程:
    • 向左照射,且原来没有未覆盖部分,最右边位置在当前灯照射左边界左边,取最右边位置后某一处$j$到当前位置作为假装覆盖实际没有覆盖部分(或者不选取),转移方程:
  • 总时间复杂度$O(n^3)$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
#define gc getchar()
#define N 109
using namespace std;
int n,x[N],l[N],num[N],L[N],R[N],a[N],b[N],dp[N][N*3][N*3],ans;
vector <int> lsh;
int read()
{
int x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-48;
return s*x;
}
bool cmp(int aa,int bb)
{
return x[aa]<x[bb];
}
int main()
{
n=read();
for (int i=1;i<=n;i++)
{
x[i]=read(),l[i]=read(),num[i]=i;
lsh.push_back(x[i]-l[i]),lsh.push_back(x[i]),lsh.push_back(x[i]+l[i]);
}
sort(num+1,num+n+1,cmp);
sort(lsh.begin(),lsh.end());
lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
for (int i=1;i<=n;i++)
a[i]=x[num[i]],b[i]=l[num[i]];
for (int i=1;i<=n;i++)
{
L[i]=lower_bound(lsh.begin(),lsh.end(),a[i]-b[i])-lsh.begin()+1;
x[i]=lower_bound(lsh.begin(),lsh.end(),a[i])-lsh.begin()+1;
R[i]=lower_bound(lsh.begin(),lsh.end(),a[i]+b[i])-lsh.begin()+1;
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=lsh.size();j++)
for (int k=j;k<=lsh.size();k++)
{
dp[i][j][max(R[i],k)]=max(dp[i][j][max(R[i],k)],dp[i-1][j][k]+max(0,lsh[R[i]-1]-lsh[k-1]));
if (L[i]<=j) dp[i][0][max(x[i],k)]=max(dp[i][0][max(x[i],k)],dp[i-1][j][k]+max(0,lsh[x[i]-1]-lsh[k-1]));
}
for (int j=1;j<=lsh.size();j++)
{
if (j<x[i])
{
dp[i][0][R[i]]=max(dp[i][0][R[i]],dp[i-1][0][j]+lsh[R[i]-1]-lsh[x[i]-1]);
for (int k=j;k<x[i];k++)
dp[i][k][R[i]]=max(dp[i][k][R[i]],dp[i-1][0][j]+lsh[R[i]-1]-lsh[k-1]);
}
else
dp[i][0][max(R[i],j)]=max(dp[i][0][max(R[i],j)],dp[i-1][0][j]+max(0,lsh[R[i]-1]-lsh[j-1]));
dp[i][0][max(x[i],j)]=max(dp[i][0][max(x[i],j)],dp[i-1][0][j]+max(0,lsh[x[i]-1]-lsh[max(j,L[i])-1]));
for (int k=j;k<L[i];k++)
dp[i][k][max(x[i],j)]=max(dp[i][k][max(x[i],j)],dp[i-1][0][j]+lsh[x[i]-1]-lsh[k-1]);
}
}
for (int i=1;i<=lsh.size();i++)
ans=max(ans,dp[n][0][i]);
printf("%d\n",ans);
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces559E

文章作者:wzf2000

发布时间:2017年12月23日 - 22:12

最后更新:2017年12月25日 - 11:12

原始链接:https://wzf2000.github.io/2017/12/23/Codeforces559E/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。