记录编号	595041	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[统一省选 2020]信号传递	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	7.421 s
提交时间	2024-10-07 09:42:25	内存使用	157.19 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 23,M = 1<<N;
const int inf = 1e9;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int n,m,k;
int f[M],g[N+2][M>>1],w[N+5][N+5],lg[M];

void cmin(int &x,int y){x = min(x,y);}
int lowbit(int x){return x & (-x);}
int main(){
	freopen("haoi2020_transfer.in","r",stdin);
	freopen("haoi2020_transfer.out","w",stdout);
	n = read(),m = read(),k = read();
	int x = 0;
	lg[0] = -1;
	for(int i = 1;i < M;i++)lg[i] = lg[i>>1] + 1;
	for(int i = 1;i <= n;i++){
		int y = read() - 1;
		if(i != 1)w[x][y]++;
		x = y;
	}
	for(int i = 0;i < m;i++){
		for(int j = 0;j < m;j++)
			if(i != j)g[i][0] += w[j][i] * k - w[i][j];
//		printf("&&&&&& %d\n",i);
//		printf("--- %d %d %d\n",i,0,g[i][0]);
		for(int S = 1;S < (1<<m-1);S++){
			int T = S - lowbit(S),j = lg[lowbit(S)];
			j += (j >= i);
			g[i][S] = g[i][T] + (w[i][j] * k + w[j][i]) - (w[j][i] * k - w[i][j]);
//			printf("--- %d %d %d\n",i,S,g[i][S]);
		}
	}
	for(int S = 1;S < (1<<m);S++){
		f[S] = inf;int cnt = __builtin_popcount(S);
		for(int j = S;j;j -= lowbit(j)){
			int v = lg[lowbit(j)];
			int T = (S & ((1 << v) - 1));
			T = T | ((S - T - lowbit(j)) >> 1);
			cmin(f[S],f[S - lowbit(j)] + g[v][T] * cnt);
		}
	}
	printf("%lld\n",f[(1<<m)-1]);

	return 0;

}