7/29 연습

2969. 메뚜기 (COCI 08/09 Contest #1 5번)

문제 : http://icpc.me/2969

오래전에 친구가 교내 대회에 냈던 문제인데, 그때 아무생각없이 $O(n^4)$이랑 $O(n^3)$ 생각하고 끝냈던 문제.

일단 $dp[i][j]$를 $(i,j)$에서의 최장 경로라고 하자. 이제 각각 $n$개씩의 행/열에 대해서 $dp$값과 좌표를 저장해두는 자료구조를 만든다.

높이가 낮아지는 순서대로 탐색하면서, i+1열, i-1열, j-1열, j+1열에 저장된 dp값들 중 조건을 만족하면서 가장 큰 dp값을 $D$라고 하면, $dp[i][j]=D+1$이 된다. 

자료구조를 맨 처음에는 set으로 했는데, set을 허투루 썼더니 메모리 초과가 났다(...) 여윽시 set/map은 사회악 (heap으로 했으면 AC가 났을지도?)

여기서 시간을 줄일 수 있는 아이디어는 한 행/열에서 dp값이 가장 큰 4개의 값만 들고 다니면, 그 4개 중에 문제의 까다로운 좌표 조건을 만족하는 놈이 반드시 존재한다는 것이다. 그래서 자료구조는 그냥 한 열당 4개짜리 배열로 충분하다.

여기서 한 가지 신경써줘야 할 점은 높이가 같은 점은 한 열에 최대 $n$개까지 존재할 수 있으므로, 이걸 고려하지 않고 바로 자료구조에 현재 dp값을 삽입하면 WA를 받게 된다. 높이가 같은 점들끼리는 따로 $tmp$같은 벡터에 저장해 두었다가 높이가 달라지는 순간 $tmp$를 비우면서 자료구조에 넣어주어야 한다.

Time Complexity : $O(\text{sort}(n^2)+n^2) = O(n^2 \lg n)$

#include <bits/stdc++.h> #define va first #define vb second using namespace std; typedef pair<int,int> ii; typedef pair<short,short> ss; const int mx=1505; ii H[mx][4], V[mx][4]; ii sh[mx*mx]; int ts; int th[mx], tv[mx]; int h[mx][mx],dp[mx][mx]; ss v[mx*mx]; int n,nr,nc; void input(){ short i,j; cin.sync_with_stdio(false); cin.tie(0); cin>>n>>nr>>nc; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ cin>>h[i][j]; v[n*(i-1)+j-1]=ss(i,j); } } sort(v,v+n*n,[](ss p,ss q)->bool{ return h[p.va][p.vb]>h[q.va][q.vb]; }); } void do_dp(){ int r,c,nowh=-1,dpmx,j; ii hi, vi; for(int i=0;i<n*n;i++){ r=v[i].va, c=v[i].vb; dpmx=0; if(h[r][c]!=nowh){ nowh=h[r][c]; for(j=0;j<ts;j++){ hi=ii(dp[sh[j].va][sh[j].vb],sh[j].vb); vi=ii(dp[sh[j].va][sh[j].vb],sh[j].va); if(th[sh[j].va]==4) *min_element(H[sh[j].va],H[sh[j].va]+4)=hi; else H[sh[j].va][th[sh[j].va]++]=hi; if(tv[sh[j].vb]==4) *min_element(V[sh[j].vb],V[sh[j].vb]+4)=vi; else V[sh[j].vb][tv[sh[j].vb]++]=vi; } ts=0; } for(j=0;j<th[r-1];j++){ if(abs(H[r-1][j].vb-c)>1) dpmx=max(dpmx,H[r-1][j].va); } for(j=0;j<th[r+1];j++){ if(abs(H[r+1][j].vb-c)>1) dpmx=max(dpmx,H[r+1][j].va); } for(j=0;j<tv[c-1];j++){ if(abs(V[c-1][j].vb-r)>1) dpmx=max(dpmx,V[c-1][j].va); } for(j=0;j<tv[c+1];j++){ if(abs(V[c+1][j].vb-r)>1) dpmx=max(dpmx,V[c+1][j].va); } dp[r][c]=++dpmx; sh[ts++]=ii(r,c); } } int main(){ input(); do_dp(); printf("%d\n",dp[nr][nc]); }