구사과

http://wcipeg.com/problem/ioi0423 O(M^2) 관찰해야 할것은 모든 엠포디아들이 Disjoint하다는 것이다. 완전한 포함 관계는 당연히 없을 거고 겹치는 것에 대해서 얘기하자면, 두 framed interval이 [a, b] / [c, d] 로 겹쳐있다면 (a < c < b < d), [a, b] / [b, c] / [c, d] 구간 모두 framed interval이다. 고로 [a, b]와 [c, d]는 엠포디아가 될 수 없다. 이러면 구간의 시작점을 감소시키면서 루프를 돌고, 해당 시작점에서의 empodia가 있으면, 끝점의 범위를 감소시켜나가면서 계속... 하는 M^2 알고리즘을 만들 수 있다. 조금 더 자세히 하자면, (i, j) 쌍을 찾을 때 i = N-1에서 감소 ..

Floyd-Warshall로 최단 경로의 개수를 셀 수가 있는데. 3중 포문을 돌면서 거리와 count를 같이 갖고 있으면서 돌리면 된다. 예를 들어 현재 Dist(j, k) > Dist(j, i) + Dist(i, k) 라서 업데이트 된다면,Count(j, k) = Count(j, i) * Count(i, k) 이고,Dist(j, k) == Dist(j, i) + Dist(i, k) 라면Count(j, k) += Count(j, i) * Count(i, k) 이다. 초기 조건은 주어지는 에지들이면 Count 1 아니면 0 이런 식이면 된다. 신기함 ㅋㅋ 연습 문제 : http://wcipeg.com/problem/noi07p1

http://wcipeg.com/problem/ccc12s2p6 먼저 아군과 적군은 cost 1, cost -1의 점으로 생각할 수 있으니 같이 생각하자.문제는 (0,0) 점에서 시작해서 돌아오는 polygon을 만들고 안에 들어있는 cost의 합을 최대화 하는 문제이다. 세 점이 한 직선에 없어서 깔끔한 문제. * N 0인 체인을 쭉 만드는 문제로 생각하자.Sum[j][k] = (A[j] - A[k] - 원점 안에 들어있는 점의 가중치합) 라고 하면 이제 동적 계획법을 돌리는데 DP[i][j] = Max(j < k) DP[j][k] + Sum[j][k] + A[j].cost 라고 돌리면 되고Sum과 DP 배열을 N^3에 계산하면 됨. * N