C++ 解法, 执行用时: 28ms, 内存消耗: 2560K, 提交时间: 2021-06-13 11:58:09

#include<cstdio>
#include<algorithm>
#define L 1<<23
#define C (c=*A++)
#define N 51
#define T 33
#define Q 25
using namespace std;

struct node{
	int f,a,b;
	bool operator<(node&x){return b==x.b?a==x.a?f<x.f:a<x.a:b<x.b;}
	bool cmp(node&x){return a+b==x.a+x.b?a<x.a:a+b<x.a+x.b;}
	node operator+(const node &x){return(node){f+x.f,a+x.a,b+x.b};}
}g[Q][T],G[Q][T];

const node t[T]={(node){1,1,2},(node){3,4,3},(node){2,2,2},(node){5,6,3},(node){6,7,5},(node){4,4,4},(node){4,5,4},(node){4,5,4},(node){3,3,2},(node){7,8,3},(node){8,10,5},(node){8,9,6},(node){8,8,6},(node){8,8,6},(node){9,10,5},(node){6,6,4},(node){7,8,5},(node){6,7,5},(node){6,7,4},(node){7,8,7},(node){7,8,5},(node){6,7,5},(node){7,8,7},(node){5,5,4},(node){5,5,5},(node){6,8,5},(node){5,6,4},(node){6,7,4},(node){7,8,5},(node){5,5,5},(node){5,6,5},(node){5,6,4},(node){4,4,2}};

const int fac[5]={0,1,2,6,24};
int test,n,k,e[T][T],a[N],b[N],c[N],q[4][4][4][4],cnt,f[Q][T],w[N],wt,ss[19];
long long F[N][Q];
char fl[L],*A=fl;

void read(int&x){char c;for(x=0;'0'>C||c>'9';);while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+c-48,C;}
void print(long long x){ if(!x)putchar(48);else{for(wt=0;x;ss[++wt]=x%10,x/=10);for(;wt;putchar(ss[wt--]+48));}}
void fix(node&a,node b){if(b<a)a=b;}
void Fix(node&a,node b){if(b.cmp(a))a=b;}

int main(){
	int l,r,i,j,s;
	for(l=0,k=1;k<=4;l=r,k++){
		for(i=0;i<k;a[i]=i,i++);
		do{q[a[0]][a[1]][a[2]][a[3]]=cnt++;}while(next_permutation(a,a+k));
		for(i=0;i<k;a[i]=i,i++);
		do{
			for(i=0;i<k;b[i]=i,i++);
			do{
				for(i=0;i<k;c[b[a[i]]]=i,i++);
				e[q[a[0]][a[1]][a[2]][a[3]]][q[b[0]][b[1]][b[2]][b[3]]]=q[c[0]][c[1]][c[2]][c[3]];
			}while(next_permutation(b,b+k));
		}while(next_permutation(a,a+k));
		for (r=l+fac[k],i=l;i<r;g[1][i]=G[1][i]=t[i],f[1][i]=t[i].f,i++);
		for(i=2;i<=fac[k];i++){
			for(j=l;j<r;g[i][j]=g[i-1][j]+t[l],G[i][j]=G[i-1][j]+t[l],f[i][j]=f[i-1][j]+t[l].f,j++);
			for(j=l;j<r;j++)
				for(s=l;s<r;s++){
					fix(g[i][e[j][s]],g[i-1][j]+t[s]);
					Fix(G[i][e[j][s]],G[i-1][j]+t[s]);
					if(f[i][e[j][s]]>f[i-1][j]+t[s].f)f[i][e[j][s]]=f[i-1][j]+t[s].f;
				}
		}
	}
	for(*(fl+fread(fl,1,L,stdin))=EOF,read(test);test--;){
		for(read(n),read(k),l=0,i=1;i<k;l+=fac[i],i++);
		for(i=n;i;w[i]=q[a[0]-1][a[1]-1][a[2]-1][a[3]-1],i--)for(a[0]=a[1]=a[2]=a[3]=1,j=0;j<k;read(a[j]),j++);
		for(r=l+fac[k],i=1;i<=fac[k];F[1][i]=f[i][w[1]],i++);
		for(i=2;i<=n;i++)
			for(j=1;j<=fac[k];j++){
				int tmp=g[j][w[i]].b,t1;long long tp=G[j][w[i]].a;
				if(F[i][j]=g[j][w[i]].a,tmp>fac[k]){
					if((t1=tmp-fac[k])&1)t1++,tmp=fac[k]-1;else tmp=fac[k];
					F[i][j]+=t1*((1ll<<i-1)-1)*k;
				}
				if(tmp>0)F[i][j]+=F[i-1][tmp];
				if((tmp=G[j][w[i]].b)>fac[k]){
					if((t1=tmp-fac[k])&1)t1++,tmp=fac[k]-1;else tmp=fac[k];
					tp+=t1*((1ll<<i-1)-1)*k;
				}if(tmp>0)tp+=F[i-1][tmp];if(tp<F[i][j])F[i][j]=tp;
			}print(F[n][1]),putchar('\n');
	}
	return 0;
}