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
http://wcipeg.com/problem/ccc14s2p3 문제에서 주어지는 명령들을 CNF 형태로 해석해보자, 1 -> 늑대인간, 0 -> 시민이다. D a b => a -> b A a b => a -> ~b CNF 형태가 유용한 점 중 하나는 그래프 이론적인 해석이 가능하다는 것이다. (예를 들어 2-SAT은 도달 가능성 == clause의 모순 여부라는 점을 활용한다.) 여기서 특히 주목할 점은 문제의 조건 대로라면 이렇게 주어진 명령을 그래프화 했을 때 트리 (사실은 포레스트) 형태의 모습이 생긴다는 것이다. 여기서는 늑대인간의 수가 K개인 경우의 수를 묻기 때문에, 이제 조건을 만족하는 경우의 수를 셀 때 트리 DP를 사용하면 된다. 트리 DP를 사용한다 하면 당장 rough하게 떠오르는 ..
- Total
- Today
- Yesterday