题意大致是这样的，一共要放 m 段括号序列，每一段放 n 个括号，也就是放 n*m个括号，再每一段中的 n 个位置分别有放左括号和右括号的代价，问最终摆放出合法的括号序列的最小代价是多少。
另外保证，n小于20，m小于1e7，m是整数
这个大概是我一年前多做的，当时在21组上T了，然后就放弃了，我也不记得当时怎么做的了，也不想看以前的代码。
很明显 n 个一段是循环的，所以肯定每个段作为一个整体考虑。为了保证括号序列的正确性，可以认为左括号为+1，右括号为-1，则正确性即过程中前缀和始终为正，最终总和为零。因此每个段的不同情况无非就是改段过程中的最小负值，以及整段的正负值。
其中最小负值范围在 [-n,0] 内，整段正负值则在 [-n,n] 内。
因此可以定义 dp 数组：
dp[i][j][n+k] 表示 考虑完 n 个位置中的前 i 个位置，最小负值的绝对值为 j ，正负值为 k 的最小代价，此处为了保证下标为正，第三维加上了 n。
则在 dp[i][j][n+k] 的基础上，考虑第 i+1 个位置取左括号还是右括号，即可进行状态转移：
dp[i+1][max(j,-(k+1))][n+k+1] = min(dp[i+1][max(j,-(k+1))][n+k+1], dp[i][j][n+k] + a[i+1]);
dp[i+1][max(j,-(k-1))][n+k-1] = min(dp[i+1][max(j,-(k-1))][n+k-1], dp[i][j][n+k] + b[i+1]);
此处第一维可以滚动掉，不过毕竟 n 很小，所以并不占太多空间，就没有管。
然后，考虑多个段进行组合，其实若干段组合起来之后，只需要记录总正负值就可以了，而考虑如果正负值达到2*n，则可以在之前就放正负值为负的，将总正负值限制在小于 2*n，即：
如果 n 为 10，则4段正负值为 10 10 -10 -10 的情况下，可以调整为 10 -10 10 -10 而保证实际情况和代价均不变。
但注意，需要保留到 2*n-1 （大概？），因为如果限制在小于 n 的话，会导致最小负值较小的不能参与转移。
然后我们就可以进行块的转移推导了：
我们可以考虑在已有正负值为 i 的情况下， 想要转移到正负值为 j 的情况，先用DP数组来表示转移。
定义 DP[x][i] 为考虑完前 x 块，总正负值为 i 的最小代价，则 DP[x-1][j] 转移到 DP[x][i] 可以这样考虑：
第 x 块的正负值为 p = i-j ，其绝对值应当小于 n，因为单块的正负值不会超过 n。
第 x 块的最大负值的绝对值 k 则不得大于 j ，k 是需要循环枚举的。
对于枚举的 i 、 j 、 k，和求得的 p，则有：
DP[x][i] = min( DP[x][i] , DP[x-1][j] + dp[n][k][n+p] )。
如果直接这样做DP，则块数有 m 个，i 和 j 均为 2n 个，k 也有 n 个，则复杂度将是 O(m * n^3)，显然会超时（虽然我不知道一年前写的是不是这样超时的）。
但是我们发现，这个状态转移非常类似矩阵乘法，只是将乘法改成加法，将加法改成min。结合 m 的范围，不难想到 1e7 必然不是用来循环遍历的，这个数据量很适合矩阵快速幂。
大概在半年前，我在某个比赛还是什么的上面接触过矩阵快速幂的改写，大约听题解是将矩阵乘法改成了加法+max，虽然没有补那个题，但是也还是有印象，就尝试着改写了一下。
主要改写的要求必然是矩阵运算的结合律：
M*(M*T) = (M*M)*T
则矩阵运算就可以将左边的 m 次变成快速幂进行运算。
我将DP的每一层写成列向量作为T，而M的每个元素则是对应位置需要加的值：
M[i][j] = min_(0<=k<=j) dp[n][k][n+p]；
并手推演算了一下样例里的矩阵进行运算，发现似乎是符合结合律的，虽然并没有进行严谨的证明，但是我还是这样改了矩阵快速幂的板子，敲了一下，结果就A掉了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f; struct mat{
int r,c;
ll m[][];
mat(){}
mat(int r,int c):r(r),c(c){}
}; void clear(mat &a){
memset(a.m,0x3f,sizeof(a.m));
} inline ll min(ll a, ll b){return a <= b ? a : b ;} mat mul(mat a,mat b){
mat tmp(a.r,b.c);
clear(tmp);
int i,j,k;
for(i=;i<tmp.r;i++){
for(j=;j<tmp.c;j++){
for(k=;k<a.c;k++){
tmp.m[i][j]=min(tmp.m[i][j], a.m[i][k] + b.m[k][j]);
}
}
}
return tmp;
} mat QP(mat a,int n){
mat ans(a.r,a.r),tmp(a.r,a.r);
memcpy(tmp.m,a.m,sizeof(tmp.m));
clear(ans);
for(int i=;i<ans.r;i++){
ans.m[i][i]=;
}
while(n){
if(n&)ans=mul(ans,tmp);
n>>=;
tmp=mul(tmp,tmp);
}
return ans;
} void print(mat a){
for(int i=;i<a.r;++i){
for(int j=;j<a.c;++j){
printf("%lld",a.m[i][j]);
if(j==a.c-)printf("\n");
else printf(" ");
}
}
} ll dp[][][];
int n,m;
int a[],b[]; int main(){
scanf("%d%d",&n,&m);
for(int i = ; i <= n ; ++ i)scanf("%d",&a[i]);
for(int i = ; i <= n ; ++ i)scanf("%d",&b[i]);
memset(dp,0x3f,sizeof(dp));
dp[][][n+] = a[];
dp[][][n-] = b[];
for(int i = ; i < n ; ++ i){
for(int j = ; j <= n ; ++ j){
for(int k = -i ; k <= i ; ++ k){
dp[i+][max(j,-(k+))][n+k+] = min(dp[i+][max(j,-(k+))][n+k+], dp[i][j][n+k] + a[i+]);
dp[i+][max(j,-(k-))][n+k-] = min(dp[i+][max(j,-(k-))][n+k-], dp[i][j][n+k] + b[i+]);
}
}
}
mat M(*n,*n), T(*n,);
clear(M);
clear(T);
for(int i = ; i < * n ; ++ i){
for(int j = ; j < * n ; ++ j){
int p = i - j;
if(abs(p) > n)continue;
for(int k = ; k <= j ; ++ k){
M.m[i][j] = min(M.m[i][j], dp[n][k][n+p]);
}
}
}
T.m[][] = ;
mat ans = mul(QP(M,m), T);
printf("%lld\n",ans.m[][]);
return ;
}