P3431 [POI2005]AUT-The Bus(2차원 편차, 트리 배열)
2차원 편차 고전 문제, 트리 그룹 유지 접두사 최대치, dp사상.
1 #define bug(x) cout< 2 #define IO std::ios::sync_with_stdio(0)
3 #define ull unsigned long long
4 #include
5 #define iter ::iterator
6 #define pa pair
7 #define pp pair
8 using namespace std;
9 #define ll long long
10 #define mk make_pair
11 #define pb push_back
12 #define se second
13 #define fi first
14 #define ls o<<1
15 #define rs o<<1|1
16 const int N=1e5+5;
17 int n,m,q;
18 int mx=1e9;
19 pp p[N];
20 int c[N];
21 int low(ll x){
22 return x&(-x);
23 }
24 void add(int x,int y){
25 while(x<=q){
26 c[x]=max(c[x],y);
27 x+=low(x);
28 }
29 }
30 int qu(int x){
31 int res=0;
32 while(x){
33 res=max(res,c[x]);
34 x-=low(x);
35 }
36 return res;
37 }
38 int a[N];
39 int main(){
40 IO;
41 cin>>n>>m>>q;
42 for(int i=1;i<=q;i++){
43 cin>>p[i].fi>>p[i].se.fi>>p[i].se.se;
44 a[i]=p[i].se.fi;
45 }
46 sort(a+1,a+1+q);
47 int na=unique(a+1,a+1+q)-a-1;
48 sort(p+1,p+1+q);
49 ll ans=p[1].se.se;
50 int x=lower_bound(a+1,a+1+na,p[1].se.fi)-a;
51 add(x,ans);
52 for(int i=2;i<=q;i++){
53 int x=lower_bound(a+1,a+1+na,p[i].se.fi)-a;
54 ll res=qu(x)+p[i].se.se;
55 ans=max(ans,res);
56 add(x,res);
57 }
58 printf("%lld
",ans);
59 } 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
