DP19 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 #591 D - Sequence Sorting (LIS유사, 투포인터, dp) https://codeforces.com/contest/1241/problem/D 최대 300000의 쿼리에 대해서 최대 300000길이의 배열을 입력받고 문제에 나온 연산을 최소한으로 수행해서 배열을 정렬한다면, 그 연산의 횟수를 출력하는 문제다. 초기의 배열을 A(앞으로 미는 연산 수행한 그룹) + B(연산수행하지않은 그룹) + C(뒤로 미는 연산을 수행한 그룹)으로 나눈다면, A의 크기와 C의 크기의 합이 정답이 된다. (여기서 크기는 그룹에 속한 숫자의 종류개수) A크기+C크기 = 초기배열의 크기 - B그룹의 크기 이므로, B그룹의 크기만 계산해주면 된다. B그룹은 초기 배열에서 이미 정렬된 최대의 길이이므로, LIS와 유사하다고 볼 수 있다. (초기배열이 1 3 1 4라면 LIS=3, 정렬된 최.. 2019. 11. 2. BOJ 1351 - 무한 수열 https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 개인적으로 매우 신박한 문제다. 대놓고 기본 dp문제인데 dp배열로 풀기엔 배열 크기가 오버된다. map을 사용해서 dp하는 문제다. #include #include #include using namespace std; map dp; long long n, p, q; long long f(long long n) { if (n == 0)return 1; auto ret = dp.find(n); if (ret != dp.end()) return ret->second; long long rst = 0; rst = f(n / p) + f(n / .. 2019. 8. 6. 이전 1 2 3 4 5 다음