【 BZOJ 】 1664: [Usaco 2006 오픈] 카 운 티 페 어 이벤트 참가 축제 (선분 수 + dp)

http://www.lydsy.com/JudgeOnline/problem.php?id=1664
아까 그 문제 랑 똑 같 네.
단지 가중치 가 1 로 바 뀌 었 을 뿐이다.
마찬가지 로 선분 트 리 로 구간 을 유지 한 후 구간 범위 내 dp.
upd: (사실 가중치 가 1 인 것 은 바로 욕심 을 낼 수 있 습 니 다.........................................................

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

#define lc x<<1

#define rc x<<1|1

#define MID (l+r)>>1

#define lson l, m, lc

#define rson m+1, r, rc

const int N=10005;

int mx[N<<8], mxi, n;

struct dat { int a, b; }a[N];

bool cmp(const dat &a, const dat &b) { return a.a<b.a; }

void pushup(int x) { mx[x]=max(mx[lc], mx[rc]); }

void update(int l, int r, int x, int key, int p) {

	if(l==r) {

		mx[x]=key;

		return;

	}

	int m=MID;

	if(p<=m) update(lson, key, p); else update(rson, key, p);

	pushup(x);

}

int query(int l, int r, int x, int L, int R) {

	if(L<=l && r<=R) return mx[x];

	int m=MID, ret=0;

	if(L<=m) ret=query(lson, L, R); if(m<R) ret=max(ret, query(rson, L, R));

	return ret;

}



int main() {

	read(n);

	for1(i, 1, n) read(a[i].a), read(a[i].b), mxi=max(a[i].a+a[i].b, mxi);

	sort(a+1, a+1+n, cmp);

	int ans;

	for1(i, 1, n) {

		if(a[i].a<=1) ans=0; else ans=query(1, mxi, 1, 1, a[i].a-1);

		update(1, mxi, 1, ans+1, a[i].a+a[i].b-1);

	}

	print(query(1, mxi, 1, 1, mxi));

	return 0;

}

 
 
 
 
Description
Farmer John has returned to the County Fair so he can attend the special events (concerts, rodeos, cooking shows, etc.). He wants to attend as many of the N (1 <= N <= 10,000) special events as he possibly can. He's rented a bicycle so he can speed from one event to the next in absolutely no time at all (0 time units to go from one event to the next!). Given a list of the events that FJ might wish to attend, with their start times (1 <= T <= 100,000) and their durations (1 <= L <= 100,000), determine the maximum number of events that FJ can attend. FJ never leaves an event early.
 
N 개의 명절 이 있 습 니 다. 매 명절 마다 시작 시간 과 지속 시간 이 있 습 니 다. 소 는 가능 한 한 많은 명절 에 참가 하고 싶 습 니 다. 가장 많이 참가 할 수 있 는 지 물 어보 세 요. 소의 이동 속 도 는 매우 빠 르 고 시간 이 걸 리 지 않 습 니 다.
Input
* Line 1: A single integer, N.
* Lines 2..N+1: Each line contains two space-separated integers, T and L, that describe an event that FJ might attend.
Output
* Line 1: A single integer that is the maximum number of events FJ can attend.
Sample Input
7
1 6
8 6
14 5
19 2
1 8
18 3
10 6
INPUT DETAILS:
Graphic picture of the schedule:
11111111112
12345678901234567890 - --- 이것 은 시간 축 입 니 다.
--------------------
111111 2222223333344
55555555 777777 666
이 그림 에서 1 은 첫 번 째 명절 을 1 부터 6 시간 동안 지속 하 는 것 을 나타 낸다.
Sample Output
4
OUTPUT DETAILS:
FJ can do no better than to attend events 1, 2, 3, and 4.
HINT
Source
Silver