DP19 Educational codeforces #69 div2 D - Yet Another Subarray Problem (dp) https://codeforces.com/contest/1197/problem/D 까다로운 dp문제 최대 3e5개의 숫자 배열이 주어진다. 연속된 부분수열 a[l..r]의 비용이 다음과 같을 때, 그 최대값을 구해라. (빈 부분수열의 비용은 0이다. 따라서 답의 최댓값은 0이다.) i번째에서 끝나는 연속된 부분수열은 다음 네 가지 경우로 나눌 수 있다. 첫번째 경우: 0 두번째 경우: a[i]-k 세번째 경우: 네번째 경우: psum(0,i)-k 이걸로 for문 디피하면된다. #include #include #include #define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); using namespace st.. 2020. 1. 5. BOJ 2228 - 구간나누기 (dp) https://www.acmicpc.net/problem/2228 최대 100자의 숫자배열을 입력 받았을 때 연속된 수열을 총 m개 뽑을 때 그 뽑힌 숫자들의 최대값을 구하는 문제. **dp값을 처음 초기화 할 때 특정 값으로 초기화 하기가 애매하다. 숫자가 음수일 수 있기 때문. 따라서 bool타입 c[101][51]을 사용해서 지금 상태가 이미 메모된 상태인지 기록해둔다. (psum 사용하므로 1-base ) f(i, j) : 1 ~ i 번째 숫자를 사용하여 j개의 연속된 수열을 뽑을 때 뽑힌 숫자들의 최댓값 f(i, j) = max(i번째 숫자를 뽑지 않을 때, i번째 숫자를 뽑을 때) 1. i번째 숫자를 뽑지 않는 경우 f(i,j) = f(i-1, j) 2. k번째 ~ i번째 숫자를 뽑는 경우 f.. 2019. 12. 29. BOJ 11049 - 행렬 곱셈 순서 (dp) https://www.acmicpc.net/problem/11049 파일 합치기와 매우 유사함 최대 500개의 행렬 정보가 n*m 형태로 입력될 때, 이들은 순서대로 곱할 수 있음이 보장된다. 모든 행렬을 곱할 때 곱셈 연산의 최소횟수를 구하는 문제. f(i, j) : i~j번째 행렬을 곱할 때 곱셈 연산의 최소 횟수 f(i, j) = f(i,k) + f(k+1,j) + a[i].f * a[k+1].f * a[j].s ( i > a[i].first >> a[i].second; memset(dp, -1, sizeof(dp)); cout 2019. 12. 29. codeforces #608 div2 D - Portals (dp) https://codeforces.com/contest/1271/problem/D dp인건 파악했는데 중요한 포인트를 놓치고 식을 너무 복잡하게 짜서 틀린 문제. 성 n개, (성의 방어력 a, 성에서 영입되는 병사 b, 성에 인원 1명을 배치했을 때 받는 점수 c), 성과성을 잇는 간선 m개, 초기 병사 수 k명이 주어질 때 얻을 수 있는 최대 점수를 출력하는 문제다. pos번째 성에 인원을 1명 배치하는 경우는 최대한 늦게 하는 것이 최적이다. 예를들어 3번째 성으로 4번 5번 성에 포탈이 있다면 3번째 성에서 바로 인원을 배치하는 것보단 4번 성에서 포탈을 태워 보내는 경우가 최적이고, 그보다 5번째 성에서 3번째 성으로 인원을 배치하는 것이 최적이란 뜻이다. 위 아이디어를 자료구조로 잘 구현해 보면.. 2019. 12. 21. 이전 1 2 3 4 5 다음
