Lucent Blog

정답은 2번!

처음에 아무 생각 없이 1번으로 해서 틀렸는데, 그때 생각은 다음과 같았다:

오른쪽 끝을 기준으로 오름차순 정렬하면 Segment[i]와 Segment[j]가 겹친다면

그 사이의 모든 선분은 무조건 Segment[i]와 겹친다!

그러니까 각 선분을 선택할 때, 최대한 많이 묶어서 넘어가면 되겠지.

하지만 여기엔 큰 함정이 있었으니.. 다음 그림과 같은 데이터에서 최적해를 구하지 못한다.

위에서 빨간 숫자는 1번으로 정렬했을 때, 연두 숫자는 2번으로 정렬했을 때 각 선분의 인덱스이다.

그림에서 중요한것은 파란 선을 그어놓은 부분인데, 보다시피 빨간 인덱스에서는 1번과 4번을 함께 없애는 것을 구현할 수 없다(1번과 3번이 겹치지 않으므로)

하지만 연두 인덱스에서는 1번과 2번이므로 이 둘을 한 번에 없앨 수 있고, 당연히 비용은 앞에서 없앨 수록 적으므로 이쪽이 최선이다.

그러므로 2번처럼 정렬하면 이후의 DP까지 했을 때 시간복잡도 O(kn^2)만에 답을 구할 수 있다.

DP테이블을 d[레이저를 쏜 횟수][몇 번째 구름까지 없앴나] 로 정의하면,

와 같이 구할 수 있다(모든 인덱스는 1부터 시작한다고 가정, d[0][0] = 0이라고 가정) -

물론 k+1부터 j까지 모든 구름이 겹치는 k만 가능!

최종 답은 d[0][n],,d[k][n]중 최솟값이다.

class BuildingHeights { public: int minimum(vector h) { int n = h.size(); vector d(n+1, INF); d[0] = 0; for (int k = 1; k <= 4000; k++) { vector b; for (int i = 0; i < n; i++) if (h[i] <= k) b.push_back(k-h[i]); sort(b.begin(), b.end()); int cur = 0; for (int i = 1; i <= b.size(); i++) { cur += b[i-1]; d[i] = min(d[i], cur); } } int ans = 0; for (int i = 1; i <= n; i++) ans ^= d[i]; return ans; } };

#define x first #define y second typedef pair< int, int > ii; vector v[2001]; vector p[2001]; vector e[2001]; vector road; vector d; vector vis; int cost[2001][2001]; const int INF(1<<27); void Find(int x) { if (vis[x]) return; vis[x] = 1; for (int i = 0; i < p[x].size(); i++) { e[p[x][i]].push_back(x); road.push_back(ii(p[x][i], x)); Find(p[x][i]); } } class DrivingPlans { public: int count(int n, vector aa, vector bb, vector cc) { vis.resize(2001, false); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) cost[i][j] = 500000; } for (int i = 0; i < aa.size(); i++) { v[aa[i]].push_back(bb[i]); v[bb[i]].push_back(aa[i]); cost[aa[i]][bb[i]] = cc[i]; cost[bb[i]][aa[i]] = cc[i]; } d.resize(n+1, INF); priority_queue< ii, vector, greater > q; q.push(ii(0, 1)); d[1] = 0; while (!q.empty()) { ii now = q.top(); q.pop(); if (d[now.y] < now.x) continue; for (int i = 0; i < v[now.y].size(); i++) { int nv = v[now.y][i], nd = now.x + cost[now.y][nv]; if (nd < d[nv]) { d[nv] = nd; p[nv].clear(); p[nv].push_back(now.y); q.push(ii(nd, nv)); } else if (nd == d[nv]) { p[nv].push_back(now.y); } } } Find(n); vector in(n+1, 0); for (int i = 0; i < road.size(); i++){ int from = road[i].x, to = road[i].y; ++in[to]; if (cost[from][to] == 0) return -1; } queue s; int dy[2001] = {0, 1}; int ans = 0; const int MOD(1000000009); for (int i = 1; i <= n; i++) { if (!in[i]) s.push(i); } while (!s.empty()) { int now = s.front(); s.pop(); for (int i = 0; i < e[now].size(); i++) { int nv = e[now][i]; dy[nv] += dy[now]; if (dy[nv] >= MOD) dy[nv] -= MOD; if (--in[nv] == 0) { s.push(nv); } } } return dy[n]; } };