mo1lusca의 블로그

https://www.acmicpc.net/problem/4008CHT의 바이블 점화식은 $DP[i] = max(\;a(S[i]-S[j])^{2}+b(S[i]-S[j] ) +c+DP[j]\;)$ 이다.$j$와 관련 없는 항은 $max$밖으로 빼줄 수 있다.$(S[i]-S[j])^{2}$를 전개한 뒤 &max& 밖으로 항을 빼주자.그럼 $DP[i] = max(\;-2aS[i]S[j] + aS[j]^{2} - bS[j] + DP[j]\;) + aS[i]^{2} + bS[i] + c$이 되고,$max$ 밖의 항들은 상수항이므로 나중에 더해줘도 된다.$max$ 안의 식은 $S[i]$에 대한 일차식으로 나타낼 수 있다.따라서 $DP[i] = max(\;-2aS[j]x + (aS[j]^{2}-bS[j]+DP[j])..

https://www.acmicpc.net/problem/13263$DP[i]$ : $i$번째 나무를 높이가 1이 되게 하는 최소비용 이다.그럼 점화식이 $DP[i] = min( A[i] * B[j] + DP[j] )\;(0\le j 이때 $A[i] * B[j]$는 $i$보다 작은 $j$에 대해, $i$번째 나무를 $j$번째 비용으로 모두 자른다는 뜻이고,$DP[j]$는 $j$번째 비용을 사용하기 위해 $j$번째 나무를 자르는걸 의미한다. 하지만 n이 100,000이라 $O(n^{2})$은 안되기 때문에....CHT를 써줘야 한다!문제 조건에 의해 $a_{i}$는 단조증가하고, $b_{i}$는 단조감소하기 때문에, CHT를 쓸 수 있다. #include using namespace std;using ll..

https://codeforces.com/contest/2171코포를 두세번정도 쳐봤었지만..진짜 실력을 키우려면 업솔빙을 해야 한다는 것을 알게 되었다.. A. Shizuku Hoshikawa and Farm Legs브론즈쯤 되는듯한 간단한 사칙연산 문제였다.n이 홀수인 경우는 불가능하니 0이다. n이 짝수인 경우만 고려하자.소의 마릿수를 정하면 닭의 마릿수는 자동으로 정해진다. (소 1마리 == 닭 2마리)n을 4로 나눈 값 + 1(소를 선택하지 않는 경우)가 정답이 되겠다.더보기include using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; if (n % 2) { cout B. Yuu Koito..