记录编号	595204	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[统一省选 2020]信号传递	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	9.372 s
提交时间	2024-10-10 19:38:12	内存使用	125.20 MiB

#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;
const int inf=INT_MAX;
int n,m,s;
int cnt[23][23];
int val[23][1<<23-1];
int dp[1<<23];
int lowbit(int x)
{
    return x&-x;
}
int main()
{
    freopen("haoi2020_transfer.in", "r", stdin);
    freopen("haoi2020_transfer.out", "w", stdout);
	scanf("%d%d%d",&n,&m,&s);
	int l;
	for(int i=1;i<=n;i++)
    {
		int x;
		scanf("%d",&x);
		x--;
		if(i>1) cnt[l][x]++;
		l=x;
	}
	for(int i=0;i<m;i++)
    {
		for(int k=0;k<m;k++)
        {
            if(k!=i) val[i][0]+=s*cnt[k][i]-cnt[i][k];
        } 
		for(int j=1;j<1<<m;j++)
		{
		    if(!(j&1<<i))
            {
			   int x=j^lowbit(j);
               int y=__builtin_ffs(j)-1; 
		       val[i][(j&(1<<i)-1)+((j^j&(1<<i)-1)>>1)]=val[i][(x&(1<<i)-1)+((x^x&(1<<i)-1)>>1)]+(s*cnt[i][y]+cnt[y][i])-(s*cnt[y][i]-cnt[i][y]);
		    }
        }
	}
	for(int i=1;i<1<<m;i++)
    {
		dp[i]=inf;
		int ppc=__builtin_popcount(i);
		for(int j=0;j<m;j++)
		{
		    if(i&1<<j)
            {
			   int x=i^1<<j;
			   dp[i]=min(dp[i],dp[i^1<<j]+ppc*val[j][(x&(1<<j)-1)+((x^x&(1<<j)-1)>>1)]);//转移方程 
		    }
        } 
	}
	printf("%d",dp[(1<<m)-1]);
	return 0;
}