CCPC 2018 온라인 경기 문제 J Hdu 6447 YJJ 's Salesman
1812 단어 데이터 구조
제목 의 대의:
2 차원 평면 지정 (0)
최대 가 치 를 구하 다.
입력: T 조 데이터, N (N 개 마을 포함) T < = 10
각 그룹의 데 이 터 는 모두 N 줄, X, Y, V 로 좌표 와 가 치 를 나타 내 고 N < = 1e5
본보기
입력:
1
3
1 1 1
1 2 2
3 3 1
출력:
3
생각:
구간 크기 를 고려 하지 않 고 dp [x] [y] 를 정의 하면 좌표 x, y 에 도달 할 때의 최대 가 치 를 나타 내 고 a [x] [y] 는 위치 가 (x, y) 인 마을 의 가 치 를 나타 낸다.
그러면 dp [x] [y] = max (dp [x - 1] [y - 1] + a [x] [y], dp [x - 1] [y], dp [x] [y - 1])
하지만 좌표 때문에 x,y<1e9
그래서 모든 좌 표를 직접 이산 화 할 수 있다.
다음은 이전 을 최적화 하 는 것 을 고려 하고,
dp [x] [y] 는 dp [1 ~ x - 1] [1 ~ y - 1] 의 최대 치 를 옮 길 수 있 습 니 다.
그러면 바로 정렬 해서 트 리 배열 로 구간 최대 치 를 유지 하면 됩 니 다.
뭐? 2 차원 나무 모양 으로 배열 하 겠 다 고? 당황 하지 말고 내 말 좀 들 어 봐.
먼저 모든 마을 에 대해 먼저 왼쪽 에서 오른쪽으로 위 에서 아래로 정렬 하면 마을 은 x 좌표 가 같다.
각 x 와 같은 좌표 에 대해 1 - (y - 1) 구간 의 최고 치 를 조회 한 다음 에 전체 열 (x 와 같은) 의 마을 정 보 를 처리 한 후에 이 열 에 각각 dp 값 을 트 리 배열 에 삽입 합 니 다 (최대 치, 위 치 는 y).
마을 의 x 좌 표를 작은 것 에서 큰 것 으로 정렬 하기 때문에 이미 존재 하 는 정 보 는 현재 마을 왼쪽 에 있 는 마을 일 수 밖 에 없다. 그리고 나무 모양 배열 은 1 - y - 1 구간 에서 가장 값 을 조회 하고 결합 하면 1 ~ x - 1 과 1 ~ y - 1 구간 에서 가장 값 이 높다.
코드 로 어떻게 실현 하 는 지 상세 하 게 보 려 면 아래 코드 의 설명 을 보십시오.
코드:
#include
#include
#include
#include
#include
#include
#define lowbit(x) (((x)&-(x)))
#define MAXN 100006
#define pr(x) printf("%d
",(x))//DEBUG
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
int c[MAXN+10];
int n,m;
inline void modify(int x,int v)
{
while(x<=MAXN)
{
c[x]=max(c[x],v);
x+=lowbit(x);
}
}
inline int query(int x)
{
int f=0;
while(x>0)
{
f=max(f,c[x]);
x-=lowbit(x);
}
return f;
}
struct vill
{
int x,y,v;
}sa[MAXN];
bool operator 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
