DP19 BOJ 11994 - Circular Barn Revisited (dp) https://www.acmicpc.net/problem/11994 dp식은 대충짜지 말자고 다짐한 문제 최대 100개의 칸으로 나뉜 원형 헛간이 있다. 각 칸마다 외부로 통하는 문이 있고 양 옆 칸으로 이동하는 문이 있다. 외부에서 내부로 통하는 문을 지나는데는 비용이 들지 않는다. 옆 칸으로 이동할 때 반드시 시계방향으로 움직여야 하고 지나간 문의 수의 제곱만큼의 비용이 든다. 현재는 소들이 모두 외부에 있고, 최대 k개의 외부 문을 열어서 각 칸에 소가 정확히 ri마리씩 들어가도록 하고 싶다. 이 때 최소 비용을 구해라. ... (구간합 때문에 1base로 구현함) 당연히 시계방향 기준으로 뒤에 있는 소가 앞에 있는 소를 추월하는 것은 최적이 아니다. 0번 문을 처음으로 열어 줄 때~ n-1번 문을.. 2020. 2. 7. BOJ 12013 - 248게임 (dp) https://www.acmicpc.net/problem/12013 dp[i][j] : 구간[i,j]~~ 40이하의 자연수가 최대 248개 주어진다. 인접한 두 수가 같다면 1을 더한 값으로 합칠 수 있다. (7,7,1->8,1) 더이상 합칠 수 없을 때까지 합친 후에 남아있는 수 중 가장 큰 수의 최대값을 구해라. dp[i][j] : i~j를 합할때 남아있는 수 중 가장 큰 수. dp[i][i]=a[i] dp[i][j] =if(dp[i][k]==dp[k+1][j]) max ( dp[i][k]+1; ) i~j간격 1부터 차례로 갱신해야 하는 것에 주의. for문의 가장 바깥에 해당하는 것이 간격임. (코드의 sz) 모든 d중 최대값이 정답 #include #include #include #include .. 2020. 2. 7. QUANTIZE - Quantization (dp, 전처리, 수학) https://algospot.com/judge/problem/read/QUANTIZE 최대 100개의 숫자 배열이 주어진다. 최대 10개의 대표 정수를 정해서(배열에 없는 값 허용) 오차 제곱의 합의 최소치를 구하는 문제. 오차 제곱의 합이 최소가 되도록 하려면 대표값을 각 집합의 평균으로 정해야 한다. (식을 미분하면 알 수 있다) 입력받은 배열을 오름차순 정렬하면, 인접한 두 숫자는 같은 대표값을 갖거나 다른 대표값을 갖는 집합의 경계이다. f(k,e,t) : k이후, 이번 집합의 처음 인덱스 e, 여태까지 분류한 집합의 수 t에 대해 오차 제곱의 합의 최소를 반환 배열의 각 숫자마다 두개의 선택지가 있다. 새로 집합만들어 그 집합의 첫번째 원소가 되거나 기존 집합에 포함되거나. cost(l,r) .. 2020. 2. 3. BOJ 1176 - 섞기 (bit, dp) https://www.acmicpc.net/problem/1176 dp using bitfield중 기본문제. 최대 16명의 학생들의 키와 k값이 주어진다. 학생들을 일렬로 배치했을 때 모든 학생들의 인접한 학생과의 키 차이가 k이초과인 경우의 수를 구해라. f(s,t) : 현재 s, 마지막으로 배치된 인원이 t인 경우의 수 ans = f(0,n) -- (t==n인 경우 아무 인원이나 배치할 수 있다. [0base]) s==(1> a[i]; memset(dp, -1, sizeof(dp)); cout 2020. 1. 22. 이전 1 2 3 4 5 다음
