codeforces 559E Gerald and Path
4553 단어 선형 DP
The trail contains a monument to the mayor of the island, and although you can walk in either directions from the monument, no spotlight is south of the monument.
You are given the positions of the spotlights and their power. Help Gerald direct all the spotlights so that the total length of the illuminated part of the path is as much as possible.
Input The first line contains integer n (1 ≤ n ≤ 100) — the number of spotlights. Each of the n lines contains two space-separated integers, ai and li (0 ≤ ai ≤ 108, 1 ≤ li ≤ 108). Number ai shows how much further the i-th spotlight to the north, and number li shows the length of the segment it illuminates.
It is guaranteed that all the ai’s are distinct.
Output Print a single integer — the maximum total length of the illuminated part of the path.
Examples input 3 1 1 2 2 3 3 output 5 input 4 1 2 3 3 4 3 6 2 output 9
[분석] 시리즈 DP를 전혀 할 줄 몰라요.http://blog.csdn.net/PhilipsWeng/article/details/50767943?locationNum=15
【코드】
//codeforces
#include
#define inf 1e9
#define ll long long
#define M(a) memset(a,0,sizeof a)
#define fo(i,j,k) for(i=j;i<=k;i++)
using namespace std;
const int mxn=105;
int n,ans;
int dp[mxn][mxn][2];
struct node
{
int w,len;
}a[mxn];
inline bool comp(node u,node v)
{
return u.wint main()
{
int i,j,k,d,p;
scanf("%d",&n);
fo(i,1,n)
{
scanf("%d",&a[i].w);
scanf("%d",&a[i].len);
}
sort(a+1,a+n+1,comp);
a[0].w=-inf;
fo(i,0,n)
fo(j,0,i)
fo(p,0,1)
{
int A=0,B=0,mx=-inf;
ans=max(ans,dp[i][j][p]);
int pre=a[j].w+p*a[j].len;
fo(k,i+1,n)
fo(d,0,1)
{
int nxt=a[k].w+d*a[k].len;
if(nxt>mx) mx=nxt,A=k,B=d;
dp[k][A][B]=max(dp[k][A][B],dp[i][j][p]+min(a[k].len,nxt-pre)+mx-nxt);
}
}
printf("%d
",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
codeforces 559E Gerald and PathE. Gerald and Path time limit per test4 seconds memory limit per test256 megabytes inputstandard input outputstandard ou...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.