목록Algorithm/Problem Solving (95)
블로그 옮겼습니다
https://csacademy.com/contest/round-36/task/tree-nodes-sets/ N p; G[p].push_back(i); } for(int i = 1; i > K; for(int j = 0 ; j > a; oper[i].push_back(a); } } dfs(1, stt); for(int i = 1 ; i
https://www.acmicpc.net/problem/1804 2*B 격자에 음식이 N개 놓여져 있다. K개의 랩을 사용하여 음식을 덮을 때 덮이는 칸의 최소 개수를 구하는 문제이다. 랩은 어느 크기로든 늘리거나 줄일 수 있다. N > K >> B; for(int i = 0 ; i > r >> c; mp[c] = mp[c] | (1
https://www.acmicpc.net/problem/11570 N N; for(int i = 0 ; i > A[i]; cout
https://www.acmicpc.net/problem/14437 정수 S 와 문자열 str 가 입력으로 주어진다. S
http://codeforces.com/contest/822/problem/C n과 k가 주어진다.n은 비행기 티켓의 개수 이다. 각 티켓에는 l,r,c 세개의 정수가 있고 l은 출국일, r은 입국일, c는 티켓 가격이다.범위는 l,r l >> r >> c; v.push_back(ticket{l,r-l+1,c,0}); v.push_back(ticket{r,r-l+1,c,1}); } sort(v.begin(), v.end()); ll ans = infl; for(int i = 0 ; i
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..
N개의 컴포넌트들이있고 판떼기가 하나있다. 판떼기는 앞면과 뒷면이있다. 각 컴포넌트를 판떼기에 모두 붙이고싶은데 하나의 컴포넌트를 앞면에 붙이는 비용과 뒷면의 붙이는 비용은 다르고각 컴포넌트마다도 비용이 또 다르다.그리고 특정 컴포넌트들은 무조건 앞면 혹은 뒷면에 부착해야 된다는 조건이 주어진다.-1 이면 뒷면에, 1이면 앞면에 붙여야하며 0이면 어떤면에 붙여도 상관없다는 것이다.그리고 M개의 제한이 주어지는데 각 제한의 내용은 특정 두 컴포넌트를 다른 면에 붙였을 때에는추가적인 비용이 발생한다는 것이다. 각 제한마다 두 컴포넌트와 추가 비용은 다르다.이 때 N개의 컴포넌트를 모두 판떼기에 붙이는 최소 비용을 구하여라. 이 문제는 min-cut 문제이다. source -> 컴포넌트 -> sink 와 같은..
http://codeforces.com/contest/821/problem/D \(n,m,k\le{10^4}\)세로 n, 가로 m 인 n * m 크기의 격자판의 (1,1) 에서 (n,m) 까지 이동하고싶다.격자판의 k개의 칸에는 불이 켜져있다. (1,1)은 무조건 켜져있다. 이동할 때에는 무조건 불이 켜져있는 칸만 밟을 수가 있다.하지만 코인 1개를 사용하면 한 행 전체, 혹은 한 열 전체의 불을 켤 수가 있다.한번에 하나의 열 또는 행만 켤 수가 있으며 만약 불을 켜는 행이나 열을 바꾸고 싶다면원래 부터 불이 켜져있던 칸으로 이동을 해야 한다. 물론 바꾸면 이전에 켠 행(열)은 원래 켜져있던 칸을 빼고는 다 꺼지고 새로운 행(열)이 켜지며 또 코인 1개가 든다.이 때 (1,1) 부터 (n,m) 까지가는..