뉴비의 PS 낙서장

Mo's algorithm 을 사용하는 문제다. 와아아아아아아앙 짝짝짝짝 각 숫자마다 list로 관리하면서 (dq[i].front-dq[i].back) 의 값이 숫자 i 의 최대 길이이다. 이제 이 숫자 i의 최대길이를 O(k) 가 아닌 O(sqrt(K)) 에 구해아 한다. 이 방법은 최대길이를 관리하는 버킷을 만들어서 sqrt(K) 개로 쪼갠다음 각 구간을 관리한다. 이러면 제일긴 길이 를 찾는방법을 O(sqrt(K)) 만에 구할 수 있다. 자세한건 코드를 보자. #include using namespace std; list dq[300005]; int n,k,Q,val,sz; int ans[300005],a[300005]; int b[300005],cnt[5000005]; struct Query { ..

\(DP[N] : N\)번째 징검다리를 건널때 나올 수 있는 경우의 수 라고 잡아보면 \(DP[N] = DP[N-1]+DP[N-2]+...+DP[1]\) 이라는 식이 나오는데 \(DP[N-1] = DP[N-2]+DP[N-3]+...+DP[1]\) \(DP[N-2] = DP[N-3]+DP[N-4]+...+DP[1]\) . . . \(DP[1] = 1\) 이제 \(DP[1]\) 부터 \(DP[n-1]\)을 \(DP[n]\) 의 식에 대입해 보면 \(DP[N] = 2^{1}(DP[N-2]+DP[N-3]+...+DP[1])=\) \(2^{2}(DP[N-3]+DP[N-4]+...+DP[1])\) \(= 2^{3}(DP[N-4]+DP[N-5]+...+DP[1])... =2^{N-2}DP[1]\) 가 나옵니다. DP..

알고리즘은 그리디 입니다. 일단 제일 가격이 낮은 숫자들로 최대한 채웁니다. 이때, 0 이 제일 싼 가격이면 그 다음으로 싼 가격의 숫자를 맨 앞에 놓고 그 뒤에 0을 쭉 붙입니다. 그러면 쓰고 남는 돈이 있는데 이 돈으로 최대한 큰 수로 바꿉니다. 각 숫자에 대해 몇개씩 살 수 있는지 나오는데 이 숫자들을 내림차순으로 나열하면 제일 큰 숫자를 만들 수 있습니다. 제가 쫌 코드를 드럽게 짜기 때문에 풀이 이해용으로만 보시기 바랍니다. #include using namespace std; typedef long long ll; int n,pl,End; ll k,x,co[15],ch[15],tmp[15]; struct Money { ll cost; int num; }a[15]; bool cmp(Money p..