P5851 (USACO19DEC) Greedy Pie Eaters P

区间 dp ，注意枚举端点 i，j，k 的顺序，模拟一下就好了，如果使用了未更新的状态，就是错的

sorry for that i don’t have a chinese input method

Functions:

g(x, l, r) means we have the largest cow which can eat pos(x) , and it can only affect pies in [l, r]

f(x, l, r) means the weight summary that we can get from a sequence of cows, and it only affect pies in [l, r]

So we have the things below:

foreach cow_i
  foreach x in range[l_i, r_i]
  	g(x, l_i, r_i) = w_i;

foreach k in [1 -> n]
  foreach i in [k -> 1], j in [k -> n]
    g(k, i - 1, j) = max(~, g(k, i, j))
    g(k, i, j + 1) = max(~, g(k, i, j))

foreach i in [n -> 1]
  foreach j in [1 -> n]
    foreach k in range[i, j]
      f(i, j) = min(~, f(i, k - 1) + f(k + 1, j) + g(k, i, j))

---