블로그 옮겼습니다

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3883 노드가 N개인 트리가 주어진다. 트리의 각 노드에 최대 한개의 식물을 놓아 간선들을 보호해야한다.식물은 세가지가 있다. 1번 : $100 이며 인접한 간선 하나 보호가능2번 : $175 이며 인접한 간선 두개 보호가능3번 : $500 이며 인접한 모든 간선 보호가능 간선을 모두 보호하기 위해 필요한 최소 비용을 구하는 문제이다. dp[i][j] : i는 현재 노드, j는 나의 부모를 연결하는 엣지를 부모가 보호해줬는지 여부 true/false 일 때인접한 간선을 모두 보호하기 위한 최소 비용 이라고 부분문제를 정의해 보자. 그럼 dp[i][0] 은 ..

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=4153 n개의 노드로 이루어진 트리가 있고 간선에는 기중치가 있다.q개의 쿼리가 주어진다.각 쿼리마다 연료의 양 x가 주어진다.루트노드부터 시작하여(루트 노드는 암시적으로 결정되어있음) 연료 x로 방문할 수 있는 최대 노드의 수를각 줄에 출력한다. 이 문제는 트리 dp 문제인데 부분문제를 두개 정의해야 한다. dp1[i][j]= 노드 i를 루트로 하는 서브트리에서부터 (현재노드포함) j개의 노드를 방문하고 돌아오는 최소비용 dp2[i][j]= 노드 i를 루트로 하는 서브트리에서부터 (현재노드포함) j개의 노드를 방문하고 안돌아와도 되는 최소비용 dp1은 d..

http://codeforces.com/contest/821/problem/E (0,0) 에서 (k,0) 까지 가는 방법의 수를 구하는 문제이다.이동을 할 때에는 세가지 방법이 가능하다. (x,y) 에서 (x+1,y-1), (x+1,y), (x+1, y+1) 이렇게 세가지 이동이 가능하다.대신 n개의 선분이 주어진다. 구간은 ai, bi, ci 로 표현되며y좌표가 ci 이면서 x좌표가 [ai,bi] 인 선분이다. 출발지에서 도착지까지 갈 때이 선분을 넘어가면 안된다. $b_i = a_{i+1}$ 라는 조건과 $a_n \le {k}\le{b_n}$ 라는 조건이 주어진다.그리고 ci 는 최대 15이며 ai,bi,k 는 10^18 이하이다. 뻔한 행렬 dp 이다. 12345678910111213141..

문제 링크 $1\leq{N}\leq{30}$$0\leq{M}\leq{30}$$1\leq{K}\leq{8}$ 이 문제는 N개의 집이있을 때 집과 집을 잇는 M개의 양방향 도로를 설치 하는 문제이다.A번 집과 B번 집을 잇는 도로를 설치하기 위해서는 01); } ll& cache = dp[u][v][k][mask]; if(cache != -1) return cache; cache = 0; cache = (cache + go(u,v+1,k,mask)) % mod; int nextmask = mask^(1

문제 링크 $2\leq{N}\leq{10^5}$$1\leq{K}\leq{200}$ 이 문제는 N개의 노드로 이루어진 트리가 주어진다. 각 노드에는 가중치가 있다.K가 주어지는데 최대 K번 가지를 칠 수 있다는 것이다. 어떤 노드 u를 가지친다는 말의 정의는노드 u를 루트로 하는 서브트리를 제거한다는 것이다. 최대 K번 가지를 쳐서 남아있는 트리의 모든 노드의가중치의 합을 최대로 하고싶을때 이 최대 가중치합을 구하는 문제이다. 우선 처음에 일반적인 트리dp 문제처럼 이렇게 풀어 보려고했었다.dp[u][v][k] : 현재 노드 u를 보고있고 v개의 자식을 이미 봐주었으며 앞으로 최대 k번 가지칠수있을 때 최대 가중치 합 이렇게 하면 부분문제의 수는 최대 N*K 개이다. 왜냐하면 (u,v) 의 쌍은 간..

문제 링크 격자의 사이즈 N,M 이 주어진다. 각 판은 '.' 또는 '1'~'9' 의 숫자이다. 그리고 n,m 이 주어지는데 n,m이란 어떠한 격자칸에서부터 시작하는 연속된 칸에 있는 수들의 합이 홀수가되어야 한다는 제약 조건에 대한 변수이다. 칸에서 아래로 n칸의 합은 홀수여야하고,오른쪽으로 m칸의 합도 홀수여야한다는 것이다. 물론 열 인덱스가 M-m+1 인 칸 까지만 적용되며행 인덱스가 N-n+1 인 칸까지만 적용된다. 이 때 '.' 인 칸에 적절한 '1'~'9'의 수를 넣어주어 위에서 말한 조건을 만족하도록 하는 방법의 수를 구하는 문제이다.일단 각 수가 홀수인지 짝수인지만 중요하기 때문에 현재 적혀있는 수가 실제로 몇이던 상관없고 짝수인지 홀수인지만중요하기 때문에 먼저 짝수는 0, 홀수는 1이라고..

$1\leq{N}\leq{50}$$0\leq{K}\lt{2^N-1}$괄호 문자열(correct parenthese sequence)의 정의는 이미 잘 알려져 있다.그리고 어떤 문자열 S가 '(' 와 ')' 로만 이루어져있는데 괄호 문자열이 아니라면 이것을 괄호ㄴㄴ문자열이라고 정의한다.N과 K가 주어진다. 길이가 N인 괄호ㄴㄴ문자열들을 사전순으로 정렬했을 때 K번째인 문자열을 찾는 문제이다.인덱스는 0부터 시작한다는 것에 주의하자. 우선 괄호 문자열의 개수를 구하는 방법을 알아보자.dp[i][j] : 이미 i개의 문자가 정해졌고 짝이 지어지지않은 열린 괄호의 수가 현재 j 개일 때 괄호 문자열의 수dp[i][j] = dp[i-1][j] + dp[i-1][j+1]왜냐하면 각각의 위치에서는 괄호를 열거..

https://community.topcoder.com/stat?c=problem_statement&pm=11514 $1\leq{N}\leq{50}$$1\leq{C}\leq{N}$$1\leq{L}\leq{50}$문자열의 개수 N개와 N개의 알파벳 소문자로만 이루어진 문자열이 주어지고,C와 L이 주어지는데, 길이 L의 문자열을 만들고 싶은데, 이 만들어진 문자열 내에 N개의 문자열들 중딱 C가지만 등장하도록 만드는 모든 문자열의 가짓수를 구하는 문제이다.우선 N가지의 문자열들 중 딱 C가지만 등장하는지 여부를 판단하려면 N개의 문자열을 동시에 하나의 긴 문자열에서등장하는지 찾아주는 알고리즘인 아호코라식 알고리즘이 필요하다는 것을 느낄 수가 있으며,N가지 중 지금까지 몇가지가 등장했는지를 알아야 ..

https://www.codeground.org/practice/practiceProbView.do?probId=36 $1\leq{M}\leq{N}\leq{500}$ N은 집의 개수 M은 재활용 쓰레기 통의 개수.수직선상의 N개의 집의 좌표가 주어질 때 M개의 쓰레기통을 적절히 배치하여각 집에서 가장 가까운 쓰레기통까지의 거리의 합이 최소가 되도록 하고 싶을 때 이 최소값을 구하는 문제이다. 일단 거리의 합이아니라 거리의 최대값이 최소가 되도록 하는 문제 같은 경우에는바이너리 서치(파라메트릭서치)로 풀 수가있다. 그리고 이 문제는 dp로 풀 수 있다. 우선 몇가지 정의를 하자. (모든 집들은 좌표로 오름차순 정렬되어있다고 가정) $X[i]$ : i번째 집의 좌표$C[i][j]$ : i번째 집부..

$2\leq{N}\leq{50}$$0\leq{A[i]}\leq{N-1}$N개의 원소로 이루어진 벡터 A가 주어진다. 벡터의 값들은 0과 N-1 사이값이며 중복되지않는다.$0\leq{K}\leq{N-2}$인 N-1가지의 K에 대해 각각 한번씩 swap(A[K], A[K+1]) 을 해야만 한다.그렇다면 이 swap을 하는 순서에 따라서 주어진 벡터의 결과값이 달라질 것이다.그렇다면 주어진 벡터가 0,1, ..., N-2, N-1 과 같은 형태로 오름차순 정렬되도록 하는 swap 순서는 총 몇가지가 있는지를구하는 문제이다. 이 문제는 DP로 풀 수가 있다. $dp[i][j]\,:\,[i,\,j]$ 의 구간을 오름 차순 정렬하는 방법의 수오름 차순 정렬이라는 것은 [i, j] 구간에 어떤 수들이 ..