题意
对于长度为(n)的序列({A_i})，可以进行两种操作：
（1）：选择一个位置(+1)或(-1)，花费为(1)
（2）：选择任意区间(+1)或(-1)，花费为(C)
一个序列的花费为将其变为(0)的最小花费
给定(K)，给定族({B_i}(iin[1,n],|B_i|=K))
(A_i)可以使可重集合(B_i)中的任意元素，求({A})的(k^n)种方案的最小花费之和
(n,c,Kin [1,50],B_{i,j}in[1,10^9])
如果看不懂下面怎么用维护分段函数的方法dp，可以先去做一下超级弱化版cf335F
做法
结论1：对于长度为(n)的序列({a_i}(a_ige 0))（假定边界(a_0=a_{n+1}=0)），如果每次只能选择任意区间（操作(2)），最小操作次数为(sumlimits_{i=1}^n max(0,a_i-a_{i-1}),sumlimits_{i=0}^n frac{|a_i-a_{i+1}|}{2})（两者没有直接关系）
proof
首先通过调整法，容易证明存在最优解每次操作都可以选择(-1)
（1）(sumlimits_{i=1}^n max(0,a_i-a_{i-1}))
考虑归纳，操作完(1sim n-1)，末尾添加(a_n)，增量显然为(max(0,a_n-a_{n-1}))
（2）(sumlimits_{i=0}^n frac{|a_i-a_{i+1}|}{2})
令(b_i=|a_i-a_{i-1}|)
每次操作将(b_l,b_{r+1})减(1)
对于此题，选择(sumlimits_{i=0}^n frac{|a_i-a_{i+1}|}{2})更方便
由于操作有可交换性，我们先使用操作(1)将序列变成({b_i})，然后操作(1)的次数显然等于(sumlimits_{i=1}^n |a_i-b_i|)
那么总的花费为：(Ccdot sumlimits_{i=0}^n frac{|b_i-b_{i+1}|}{2}+sumlimits_{i=1}^n |a_i-b_i|)
令(f_{i,j})为(b_i=j)时前(i)个数的最小花费（为方便计算，避免分数的出现，将花费( imes 2)）
结论2：(f_{i})为凸函数，且为一次函数的分段函数
proof
忽略(2|a_i-j|)，其显然不影响我们的结论
对(i=1sim n)施归纳
考虑(f_{i-1})对(f_i)的转移
对于(f_{i-1})上某点(j)（((j,f_{i-1,j}))），设其斜率为(k)
（1）：(|k|le C)，则(f_{i,j})必定由(f_{i-1,j})转移过来
（2）：(k<-C)，则(f_{i,j})由(f_{i-1,j'})转移（(j')是离(j)最近的斜率(ge -C)的位置）
（3）：(k>C)，则(f_{i,j})由(f_{i-1,j'})转移（(j')是离(j)最近的斜率(le C)的位置）
现在我们已经大概知道了(f)的样子，考虑(f_i)与(f_{i-1})的函数间的联系（先不考虑(2|a_i-j|)）
（1）：对于(|k|le C)，其值不变
（2）：对于(k<-C)的部分，其斜率变为(-C)
（3）：对于(k>C)的部分，其斜率变为(C)
再考虑进(2|a_i-j|)
（4）：(a_i)左边的部分，斜率(-2)；(a_i)右边的部分，斜率(+2)
令(g_{i,j}=f_{i,j}-f_{i,j-1}(j>0))，(g_{i,0}=f_{i,0})
那么对于(g_{i-1})到(g_i)的转移
（1）对(-C)取(max)，对(C)取(min)
（2）([1,a_i])整体减(2)，((a_i,infty))整体加(2)
对于(g_{i,0})根据dp的定义，有：
由于(g_{i,j}(j>1))关于(j)单调不降，有
令(a_{n+1}=0)，答案即为(g_{n+1,0}=sumlimits_{i=0}^n (2a_i+sumlimits_{j=1}^{infty} min(0,g_{i,j}+C)))
下面考虑计数
我们怎么统计(k^n)的答案呢？
观察1：(j)的范围只会达到(max{a_i})
观察2：若我们对({a_i})排序得到序列({c_i})，(forall i,jin[1,n],g_{j,v}(vin(c_{i-1},c_{i}]))均相同
proof
考虑归纳，根据(g_{i-1})到(g_i)的转移易证
观察3：(forall i,g_iin[-C-2,C+2])
proof
每次转移时会缩紧
我们将({B_{i,j}})排序，对(jin (l,r])的(g_{i,j}(iin[1,n]))统计
令(h_{i,k})为上述状态中(g_{i,j}=k)的方案数，具体转移可以看一下代码
时间复杂度(O(n^2KC))
坑点：注意(g_{0,j})的初始值为(|j-0|C)