본문 바로가기

알고리즘/코드포스44

Educational round #73 D - Make the fence great again (dp) https://codeforces.com/contest/1221/problem/D 한 부분 당 최대 2만큼 늘릴 수 있다는 것을 가정하고 dp모양은 만들었지만 예외가 있을 거라 생각하고 삽질함.. i==0일 떈 그냥 0~2번 다 확인해주고 i>0 일 떈 i-1의 상태와만 비교해주고 인자로 본인이 얼마나 늘렸는지만 같이 넘겨주면 된다. #include #include using namespace std; typedef long long ll; const ll MAX = 3e5 + 1; const ll INF = 1e18 + 1; int n; ll dp[MAX][3]; int h[MAX], c[MAX]; ll f(int k, int x) { if (k == n) return 0; ll& ret = dp[k].. 2019. 11. 7.
codeforces #581 div2 C - Anna, Svyatoslav and Maps ( 플로이드 ) https://codeforces.com/contest/1204/problem/C 루프가 없는 단방향 그래프에 대해, 임의의 경로를 입력으로 주고, 그 입력의 처음과 끝은 그대로이지만 경로는 똑같을 수 밖에 없는 정점의 배열을 출력하는 문제. (물론 그 배열의 크기는 최소가 되도록.) 위와 같은 그래프와 입력이 1 2 3 4 1 2 3 4 일떄 출력은 1 2 4 2 4 이다. 1 3 4 2 4가 안되는 이유는 3번 정점을 방문하면 입력한 경로에서 벗어나기 때문이다. 풀이) 1. 첫번째 정점과 마지막 정점은 항상 출력해야 한다. 그리고 int arr[]에 입력 경로가 담겨있고, vector ans에 출력할 정답을 담는다고 하자. (pair엔 정점번호, 입력배열에서의 인덱스) 여기서 인덱스를 저장하는 것은 .. 2019. 11. 4.
codeforces #597 div2 D - Shichikuji and Power Grid ( MST ) https://codeforces.com/contest/1245/problem/D 도시(최대 2000)마다 좌표, 파워설치비용, 간선연결가중치가 주어진다. 0번도시를 dummy vertex로 두고, 이 도시랑 연결하는 비용을 파워 설치 비용으로 둔 후, 모든 간선을 정렬하여 mst를 수행한다. mst를 뽑을 때 한 쪽 정점이 0번도시라면 그 도시는 파워를 설치한 도시이고, 양쪽 다 0번이 아니라면 두 도시는 연결된 도시이다. #include #include #include #include using namespace std; typedef pair P; typedef long long ll; const int MAX = 2001; struct Edge { int u, v; ll w; Edge(int u1.. 2019. 11. 4.
codeforces #597 div2 C - Constanze's Machine ( 피보나치 , 구현) https://codeforces.com/contest/1245/problem/C 단어를 입력하면 m은 nn으로, w는 uu로 바꿔서 출력하는 기계가 있다. (출력에 m이나, w가 나올 수 없다. 이경우 0 출력) 예를들어 단어에 nnn이라는 문자배열이 있다면, 가능한 입력은 nnn mn nm 총 세가지가 존재한다. 'n'이 k번 연속한 문자배열을 만들 수 있는 입력은 피보나치 수열을 이루게 된다. (왜 그런지는 모르겠다. 몇번 해보니까 규칙이 보임) 따라서 단어에서 n이 나오는 idx를 기록한 idx_n과 u가 나오는 idx를 기록한 idx_u에 대해서 적절히 연산해 주었다. #include #include #include using namespace std; const int MAX = 1e5+1; .. 2019. 11. 3.

티스토리툴바