Welcom to muoii’s notebook!
:)))
DYMANIC PROGRAMMING
1. optimization:
-
Knuth: dp[i][j]= min{(dp[i][k]+dp[k][j])}+ cost(i,j) |with k: i<k<j|
-
extrem(i,j)=argmin(i<k<j) (dp[i][k] + dp[k][j])
-
extrem(i,j-1)≤extrem(i,j)≤extrem(i+1,j) when and only when:
-
a≤b≤c≤d
-
quadrangle inequality: cost(a,c)+cost(b,d) ≤ cost(a,d)+cost(b,c)
-
monotonicity: cost(b,c)≤cost(a,d)
-
-
-
Divide and Conquer Optimization:
-
condition: extrem(i)≤extrem(i+1)
-
example: http://codeforces.com/contest/321/problem/E
-
-
Convex hull trick:
2. math skill
-
problem 1: Ta có 1 dãy n giá trị p[1], p[2],.., p[n] và yêu cầu tính sum(p)
-
Đơn giản, bài toán này có thể chạy qua tất cả các giá trị rồi cộng dồn để tính ra kết quả, ez…
-
Tuy vậy, trong một số bài toán thì n quá lớn, ta có thể ứng dụng công thức dựa vào giá trị của dãy:
-
Gọi lower(x) là số giá trị p[i] có giá trị >=x
-
sum(p) = lower(1) + lower(2) + … + lower(max(p))
-
-
GRAPH ALGORITHM
DATA STRUCTURE
STRING PROCESSING
KMP:
Aho:
Suffix tree:
Palindrome tree:
NUM THEORY
FFT
GEOMETRY
last :))