1. 지우개 https://www.acmicpc.net/problem/11881 Solution 1 : dp[i][j] = A(a1) < A(a2) ... < A(aj) N - K개의 점을 지났다라고 정의하겠습니다. dp[i][j] = i번 점을 j번째로 지났다 라고 정의하면, 다음과 같은 점화식을 유도할 수 있습니다.dp[i][j] = Min(dp[i-1][k] + |Xj - Xk| + |Yj - Yk|) for all 1 = 2) 시간 복잡도는 O(N^3). 3. 신기한 키보드https://www.acmicpc.net/problem/1796 고정된 알파벳에 대해서 생각해보면 각각의 알파벳의 위치는 딱히 중요하지 않습니다. 'a'를 값으로 가지는 가장 왼쪽 / 오른쪽 만 찍고 오면 되니까요.dp[i][..
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=249좀 많이 입풀이라... 가려 듣길 부탁한다 ㅠㅠ D : Travel검증되지 않은 풀이다. 제대로 읽었다면 s - t, u - v를 잇는 vertex-disjoint path를 찾는 문제로, maximum flow를 짰고 틀렸다. 데이터탓이라고 정신승리후 끝냄. E : Roommate 옛날에 AC했었다. 풀이는 대충... 이랬던거 같다.dp[i][j][t1][t2] -> 지성(0번)이 i번 task까지 "완벽히" 완료했으며, 영표(1번)가 j번 task까지 "완벽히" 완료했고, t1번째 사람이 i+1 / j+1번째 task를 t2 시간동안 돌렸다.점..
- Total
- Today
- Yesterday