[Nowcoder] [뉴커넷 NOIP 경기 전 훈련 TG4C] 살충[dp]

제목: N N 대 구간, 각 구간 [p i -3 l i, p i] [pi-li, pi] [pi -3 li, pi]와 [p i, p i + r i] [pi, pi+ri] [pi, pi+ri] 두 개 중 하나만 선택할 수 있습니다.최대 덮어쓰기를 원합니다.N ≤ 1 0 3 N\le10^3 N≤103.
이산화pi pi pi에 따라 작은 구간에서 큰 구간으로 정렬합니다.차례차례 갱신하다.F[i] [j] F[i] [j] F[i] [j]를 입력하고 ii 구간을 업데이트한 후 Po s [1] Pos[1] Pos[1] Pos[1] 부터 Po s [j] Pos[j] Pos[j] Pos[j]의 최대 덮어쓰기를 기록합니다.
초기화 F [i] [j] = F [i -3 1] [j] F [i] [j] = F [i-1] [j] F [j] = F [i -3 1] [j].
왼쪽 선택: l a s = F [i -3 1] [p i -3 l i] las=F [i-1] [pi-li] las=F [i -3 1] [pi -3 li].jj j는 p i -3 l i + 1 pi-li+1 pi -3 li+1에서 p i pipi, F [i] [j] = m a x(F [i] [j], l a s + P o s [j], P o s [p i - l i i]) F [i] [j]=max(F] = max(F [j], las + Pos [j]-Pos [pi i i]) F [i] [j]] [i] [j]]], [j]P i]+ Pos] [Pos].덮어쓰면 됩니다.오른쪽에 pi-3-l i pi-li pi-3-li 까지 덮어씌울 구간이 있는지에 대해서는 정말 있다면 왼쪽을 선택할 필요가 없기 때문에 상관없다.스케줄러: 어차피 있으면 나중에 덮여.
오른쪽: l a s = F [i -3 1] [p i] las=F [i-1] [pi] las=F [i -3 1] [pi]를 선택합니다.jj j는 p i + 1 pi+1 pi+1에서 p i + r i pi+ri pi+ri, F [i] [j] = m a x(F [i] [j]], l a s + P o s [j] - - - P o s [p i]) F [i] [j] = max(F [j] [j], las + Pos [j] - Pos [pi i]) F [j] [j] = max(F [j], las + Pos [j] [j] [Pos] [j]].i d [j] id [j] id [j]는 j j가 어떤 p i pipi일 때 그 구간에 속하는 번호 (이산화 정렬 후) 이다.jjj마다 F [i] [j] F [i] [i] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] F[j] [j] [j] [j] [j] 업데이트 후 l a s = m a x (l a s = x (l a s = max (las, F [i-1] [li {id[j]]] [l i d [j]]] [j]] [j] [j] [j] [j]] [j] [j] [j] [j]] [j] [j]]]]]]]를 업데이트한 후 I jjj j j j j j j j j j j j j j j] 를 업데이트한 사람마다 +Pos[pii] - Pos[liid[j]) 오른쪽과 왼쪽의 차이가 있는데, 한 가지 이유는 왼쪽을 선택할 때,부딪힌 것은 모두 이전에 처리한 것이다.오른쪽을 쓸었을 때 만나는 구간은 모두 장래에 처리할 구간이다.그리고 이 구간의 왼쪽 단점이 p i pi 왼쪽에 있고 오른쪽 단점이 p i + r i pi +ri pi +ri 왼쪽에 있다는 것을 알면 이 구간과 현재 처리된 오른쪽 구간 사이에는 왼쪽을 포함하는 관계가 없습니다. 처리된 F F F는 왼쪽 구간에 최종적으로 기여할 수 있습니다. (덮어쓰면 철저하게 덮어씌워집니다.)오른쪽에 있는 것을 선택하십시오. 만약 앞으로 이것과 교차할 구간을 고려하지 않는다면, 처리된 F F F F는 선택한 오른쪽 구간과 관련이 있을 뿐만 아니라, 장래에도 바뀔 수 있습니다. (p i pi pi 이전 부분은 새 구간으로 덮어쓸 수 있기 때문입니다.)그러나 앞으로 이 오른쪽 구간을 선택하지 않을 것이다. 지금 왼쪽 상태가 확실하지 않아 오른쪽 구간을 선택하는 것이 왼쪽 구간을 선택하는 것보다 못하다면 이 오른쪽 구간의 공헌이 바뀐 후에 더 좋을지 고려할 기회가 없을 것이다.그러니 장래의 공헌을 제때에 고려해야 한다.좀 엉망으로 썼으니 스스로 이해하기가 쉬울 것 같다.
마지막으로 왼쪽에서 오른쪽으로 최대 덮어쓰기를 업데이트합니다.이렇게 하면 여기에서 도대체 왼쪽 구간을 고를지 오른쪽 구간을 고를지 결정하는 것이다.F [ i ] [ j ] = m a x { F [ i ] [ k ] } , k ∈ [ 1 , j − 1 ] F[i][j]=max\{F[i][k]\},k\in[1,j-1] F[i][j]=max{F[i][k]},k∈[1,j−1]
처음에 이 문제를 받았을 때 F[N][2]F[N][2]F[N][2]...
기초적인 사고방식은 분리해서 고려하고 순서대로 구간을 고르는 것이다. 어떤 구간을 처리하고 나서 가장 좋은 답안을 기록하는 것이지 왼쪽과 오른쪽의 답안을 분리해서 기록하지 않는다.이렇게 하면 본 문제에서는 오히려 처리하기 어렵다.영향을 받는 것은 이전 구간에서만 오는 것이 아닐 수도 있기 때문이다.영향의 고려는 마땅히 전반적인 것이어야 한다
왼쪽 구간 답안과 오른쪽 구간 답안을 각각 처리할 수 있다고 생각하면 마지막으로 한 번 훑어보면 끝부분에서 본 라운드의 최대 커버를 받은 다음에 두 구간을 어떻게 해야 할지 다시 생각해 볼 수 있다.구체적인 사고방식 위에서 이미 설명하였는데, 어느 정도는 전체의 2점 같다
약화시키다

#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define adpt(p,l,r) pt[++pt[0]]=p,pt[++pt[0]]=p-l,pt[++pt[0]]=p+r
int N;
struct sut
{
	int pi,li,ri;
	sut (int a=0,int b=0,int c=0) { pi=a; li=b; ri=c;}
	bool operator < (const sut&od) const { return pi<od.pi;}
}st[3005];
int pt[9005]={},id[9005]={},F[3005][9005]={}; //    F[][]    
int main()
{
	scanf("%d",&N);
	for(int i=1;i<=N;++i)
	{
		scanf("%d%d%d",&st[i].pi,&st[i].li,&st[i].ri);
		adpt(st[i].pi,st[i].li,st[i].ri);
	}
	
	sort(st+1,st+1+N); 
	sort(pt+1,pt+1+pt[0]); 
	pt[0]=unique(pt+1,pt+1+pt[0])-pt-1;
	for(int i=1;i<=N;++i)
	{
		st[i].li=lower_bound(pt+1,pt+1+pt[0],st[i].pi-st[i].li)-pt;
		st[i].ri=lower_bound(pt+1,pt+1+pt[0],st[i].pi+st[i].ri)-pt;
		st[i].pi=lower_bound(pt+1,pt+1+pt[0],st[i].pi)-pt; //
		if((!id[st[i].pi])||(st[id[st[i].pi]].li>st[i].li))id[st[i].pi]=i;
	}
	
	for(int i=1;i<=N;++i)
	{
		for(int j=1;j<=pt[0];++j)F[i][j]=F[i-1][j];
		for(int j=st[i].li+1;j<=st[i].pi;++j)F[i][j]=max(F[i][j],F[i-1][st[i].li]+pt[j]-pt[st[i].li]);
		for(int las=F[i-1][st[i].pi],j=st[i].pi+1;j<=st[i].ri;++j)
		{
			F[i][j]=max(F[i][j],las+pt[j]-pt[st[i].pi]);
			if(id[j]&&st[id[j]].li<st[i].pi)las=max(las,F[i-1][st[id[j]].li]+pt[st[i].pi]-pt[st[id[j]].li]);
		}
		for(int premax=F[i][1],j=2;j<=pt[0];++j)premax=max(premax,F[i][j]),F[i][j]=premax;
	}
	
	printf("%d",F[N][pt[0]]);
	
	return 0;
}