블로그 옮겼습니다

문제 링크 \(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개의 물통이 있고 L리터의 물을 N개의 각 물통에 나눠서 채우려고 하는데,물통에는 상한과 하한이 있어서 각 물통에 채울 수 있는 물의 양은 이 상한과 하한 사이의 양이어야만 한다. 이 때 N개의 물통에 채운 물의 양 중에서 가장 많은 양과 가장 적은 양의 차이가 최소가 되도록 하고싶다.이 떄의 차이를 구하는 문제이다. 단, 들어오는 입력들은 항상 L리터를 상, 하한에 맞춰 분배할 수 있는 방법이적어도 하나는 있다고 가정한다. 일단 이 문제는 두가지의 풀이가 있다.첫번째 풀이는 라인 스위핑(+그리디)이다. 내가 대회 때 푼 방법이 이 라인 스위핑인데대회가 끝나고 보니 나 말고는 라인스위핑으로 푼사람을 찾을 수가 없었다.좋은건지 안좋은건지.. 사실 처음에 다른 풀이 방법을 떠올렸다가 ..