LG 2511 [HAOI2008]木棍分割

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转首先二分出最大一段的最小值,然后$dp$找出方案数设$f[i][j]$表示前$j$个分成$i$组的方案数,求出的最小值为$x$$f[i][j] = \sum(f[i-1][k])(S_j-S_k \le x,k \le j-1)$$\Theta(n^3m)$当然会$TLE$我们发现只要找到最小的$k$之后$[k,j-1]$都是合法的这时我们就可以前缀和优化$dp$设$sum[i][j] = \sum_{k=0}^j f[i][k]$$f[i][j]=sum[i-1][j-1] - sum[i-1][……