P3431 [POI 2005] AUT - The Bus [나무 모양 배열 + 이산 화] [2 차원 편차]

13803 단어 데이터 구조 - 트 리 배열ACM 문제 와 알고리즘
제목:
n * m 범위 내 k 개 점 1 ≤ n ≤ 1 0 9, 1 ≤ m ≤ 1 0 9 1 \ \ \ leq n \ \ \ leq 10 ^ 9, 1 \ \ leq m \ \ \ leq 10 ^ 9 1 ≤ n ≤ 109, 1 ≤ m ≤ 109 까지 (0, 0) 에서 출발 하여 (n, m) 매번 위로 이동 하거나 오른쪽으로 이동 할 수 있 으 며, 경험 한 경로 의 최대 가중치 를 구 할 수 있 습 니 다.
생각:
즉, 우리 가 경험 한 x i ≤ x i + 1, y i ≤ y i + 1 xi \leq x_{i+1},y_i \leq y_{i + 1} xi ≤ xi + 1, yi ≤ yi + 1 즉 2 차원 편차, 최대 접두사 와 y 좌표 정렬, 이산 화 트 리 배열, 구간 수정 유지 최대 접두사 와 구간 조회 로 최대 접두사 와 그 다음 에 점 을 x 좌표 에 따라 정렬 합 니 다.
AC_code: 
/*
Algorithm:
Author: anthony1314
Creat Time:
Time Complexity:
*/
#include
using namespace std;
const int MAXN = 1e5+5;
int bit[MAXN];
int cnt = 0;
struct node {
	int x, y, val;
} p[MAXN];
bool cmp1(node aa, node bb) {
	return aa.y < bb.y;
}
bool cmp2(node aa, node bb) {
	if(aa.x == bb.x) {
		return aa.y < bb.y;
	}
	return aa.x < bb.x;
}
int lowbit(int x) {
	return x&(-x);
}
void add(int i,int x) {
	while(i<=cnt) {
//		bit[i]+=x;
		bit[i] = max(bit[i], x);
		i+=lowbit(i);
	}
}
int sum(int i) {
	int s=0;
	while(i>0) {
//		s+=bit[i];
		s = max(s, bit[i]);
		i-=lowbit(i);
	}
	return s;
}

int main() {
	int n, m, k;
	cin>>n>>m>>k;
	for(int i = 1; i <= k; i++) {
		scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].val);
	}
	// y      
	sort(p+1, p+1+k, cmp1);
	int now = p[1].y;
	p[1].y = ++cnt;
	for(int i = 2; i <= k; i++) {
		if(p[i].y != now) {
			now = p[i].y;
			p[i].y = ++cnt;
		} else {
			p[i].y = cnt;
		}
	}
	//  x      y         
	sort(p+1, p+1+k, cmp2);
	int res;
	int ans = 0;//        
	for(int i = 1; i <= k; i++) {
		res = sum(p[i].y)+p[i].val;
		//cout<
		add(p[i].y, res);
		ans = max(res, ans);
	}
	cout<<ans<<endl;

	return 0;
}
Twilio와 Python을 사용하여 브라우저에서 전화를 걸다
JavaScript 배열 의 push () 등 방법 사용

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage