orz zhy，又被爆杀了。
首先四方 DP 是 trivial 的，我们设 \(f_{l,r,d}\) 表示 \([l,r]\) 的区间内被合并成 \(d\) 个石子的最小代价，对于 \(d>1\) 的位置 DP 完后可以贡献到 \(d=1\) 的位置。
其实这个做法可以直接通过本题（跑得飞快）可能有些卡常，所以这里需要对于同一个 \(l\) 滚动空间，然后为了在复杂度瓶颈处访问连续需要交换两维。
#include <cstdio>
using namespace std;
const int N=403;
const int INF=0x7fffffff;
int f[N][N],g[N][N];
inline void chmn(int &x,int v){if(x>v) x=v;}
int n,cl,cr;
int read(){/*...*/}
int s[N];
int main(){
int tc=read();
while(tc--){
n=read();cl=read();cr=read();s[0]=0;
for(int i=1;i<=n;++i) s[i]=read()+s[i-1];
for(int i=0;i<=n;++i)
for(int j=0;j<=n;++j) f[i][j]=g[i][j]=INF;
for(int l=n;l;--l){
g[l][l]=0;
f[1][l]=0;
for(int r=l+1;r<=n;++r){
g[r][l]=INF;
for(int t=2;t<=r-l+1&&t<=cr;++t){
register int tmp=INF;
for(register int p=l+t-2;p<r;++p)
if(f[t-1][p]!=INF&&g[r][p+1]!=INF) chmn(tmp,f[t-1][p]+g[r][p+1]);
if(cl<=t&&t<=cr&&tmp!=INF) chmn(g[r][l],tmp+s[r]-s[l-1]);
f[t][r]=tmp;
}
f[1][r]=g[r][l];
}
}
if(g[n][1]==INF) puts("0");
else printf("%d\n",g[n][1]);
}
return 0;
}
接下来是神 zhy 的福音：考虑这样一个问题，对于一个序列，给出每个区间的代价 \(w_{l,r}\)，问对于每一个区间 \([l,r]\) 将其划分成 \(x\) 个区间，满足 \(x\in[L,R]\)，求划分出来的区间的最小代价和。
对于 \(L=R\) 是经典的 \((\min,+)\) 卷积快速幂，我们只需要求出 \(W^L\) 就可以了。
对于 \(x\in[L,R]\) 的问题，实际上就相当于求 \(\sum_{i=L}^R W^i\)（当然这里的广义矩阵加法定义为对应位置取 \(\min\)）。我们把它化成 \(W^L \sum_{i=0}^{R-L} W^i\) 右边也可以通过分治的手段轻松计算。
对于这道题，事情似乎没有这么简单，因为此题的 \(w_{l,r}\) 需要由 \(f_{l,r,d}\) 决定，而 \(f\) 又需要 \(w\) 矩乘得来。这个特点令我们回想起了“半在线卷积”这个东西。
有些结构可以天然的支持半在线卷积，比如集合幂级数乘法。本题的矩阵也是如此，我们可以按照区间从小到大的顺序转移。
说了这么多还是感觉很抽象怎么办？我们可以这样理解：普通做法外层快速幂内层矩阵乘法，半在线做法外层矩乘内层做一个类似快速幂的东西。
这本质上还是一个 DP，只不过第三维从 \(d\) 变成了一个类似“快速幂自动机”的东西（大家可以意会，这东西当然跟真正的自动机没什么关系）。比如说，我们可以设 \(f_{l,r,t}\) 表示将 \([l,r]\) 划分成 \(2^t\) 个区间的最小代价，它可以由 \(f_{\times,\times,t-1}\) 的状态转移过来。也可以设 \(g_{l,r,t}\) 表示划分成 \([1,2^t]\) 个区间的最小代价，可以由 \(g_{\times,\times,t-1}\) 和 \(f_{l,r,t}\) 转移而来。
然而我蠢了没推太清楚内层的转移，于是用了一个常数稍大的写法：直接将 \([L,R]\) 像 ST 表一样拆成两个区间 \([L,L+2^k-1],[R-2^k+1,R]\)，用 \(f\) 一位一位地拼出 \(L-1\) 和 \(R-2^k\) 再直接和 \(g_{\times,\times,k}\) 拼一起，结果最后比 \(O(n^4)\) 的写法优秀不了多少。如果想要完全用半在线矩乘推的可以看看 zhouhuanyi 的写法。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef unsigned int ui;
ui read(){/*...*/}
const int N=403;
const ui INF=0x5fffffff;
inline void chmn(ui &x,ui v){if(x>v) x=v;}
ui f[N][N][9],g[N][N][9],dpa[N][N][9],dpb[N][N][9],s[N];
// f -> 2^t
// g -> 1 to 2^t
int n,cl,cr;
int ac[9],ap;
int bc[9],bp;
const char NoSol[3]="0";
int main(){
int tc=read();
while(tc--){
n=read();cl=read();cr=read();
for(int i=1;i<=n;++i) s[i]=read()+s[i-1];
if(n==1){puts("0");continue;}
if(cl>cr){puts(NoSol);continue;}
if(cl==1&&cr==1){puts(NoSol);continue;}
if(cl==1) ++cl;
if(cl==cr){
int a=cl;
ap=0;
for(int t=0;t<9;++t) if(a>>t&1) ac[ap++]=t;
for(int len=1;len<=n;++len)
for(int l=1,r=len;r<=n;++l,++r){
for(int t=1;t<ap;++t){
dpa[l][r][t]=INF;
for(int p=l;p<r;++p) chmn(dpa[l][r][t],dpa[l][p][t-1]+f[p+1][r][ac[t]]);
}
for(int t=1;t<9;++t){
f[l][r][t]=INF;
for(int p=l;p<r;++p) chmn(f[l][r][t],f[l][p][t-1]+f[p+1][r][t-1]);
}
f[l][r][0]=INF;
if(l==r) f[l][r][0]=0;
dpa[l][r][0]=f[l][r][ac[0]];
chmn(f[l][r][0],dpa[l][r][ap-1]+s[r]-s[l-1]);
chmn(dpa[l][r][0],f[l][r][ac[0]]);
}
}
else{
int k=__lg(cr-cl+1);
int a=cl-1,b=cr-(1<<k);
ap=bp=0;
for(int t=0;t<9;++t){
if(a>>t&1) ac[ap++]=t;
if(b>>t&1) bc[bp++]=t;
}
for(int len=1;len<=n;++len)
for(int l=1,r=len;r<=n;++l,++r){
for(int t=1;t<ap;++t){
dpa[l][r][t]=INF;
for(int p=l;p<r;++p) chmn(dpa[l][r][t],dpa[l][p][t-1]+f[p+1][r][ac[t]]);
}
for(int t=1;t<bp;++t){
dpb[l][r][t]=INF;
for(int p=l;p<r;++p) chmn(dpb[l][r][t],dpb[l][p][t-1]+f[p+1][r][bc[t]]);
}
for(int t=1;t<9;++t){
f[l][r][t]=INF;
for(int p=l;p<r;++p) chmn(f[l][r][t],f[l][p][t-1]+f[p+1][r][t-1]);
}
f[l][r][0]=INF;
for(int p=l;p<r;++p){
chmn(f[l][r][0],dpa[l][p][ap-1]+g[p+1][r][k]+s[r]-s[l-1]);
chmn(f[l][r][0],dpb[l][p][bp-1]+g[p+1][r][k]+s[r]-s[l-1]);
}
if(l==r) f[l][r][0]=0;
dpa[l][r][0]=f[l][r][ac[0]];
dpb[l][r][0]=f[l][r][bc[0]];
g[l][r][0]=f[l][r][0];
for(int t=1;t<=k;++t){
g[l][r][t]=f[l][r][0];
for(int p=l;p<r;++p) chmn(g[l][r][t],g[l][p][t-1]+g[p+1][r][t-1]);
}
}
}
if(f[1][n][0]==INF) puts(NoSol);
else printf("%u\n",f[1][n][0]);
}
return 0;
}