Luogu

题外话：

我可能是傻逼，

但不管我是不是傻逼，

我永远单挑出题人。

看数据范围可以确定状压dp。

$ dp[s] $ 表示s集合去代替前几个数的话现有部分的最小结果。

将数组转化成数字之间的带权图，预处理集合和点之间的单向边数量就能解决。

对于一对相邻的转化完之后数 $ a,b $ ，贡献为

\[-a+b(ab)
\]

由此状压dp得出解。

时间复杂度实际上比 $ O( m 2^{m} ) $ 低的多可以过，

但这样由于空间限制只有70pts：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long lint;
template<typename TP>inline void read(TP &tar)
{
    TP ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){ret=ret*10+(ch-'0');ch=getchar();}
    tar=ret*f;
}
namespace RKK
{
const int N=21,S=1<<21;
int n,m,c,ful;
int lb[S],cb[S];
int a[100011];
int mg[N][N],mp[S][N],mn[N][S];
int dp[S];

int main()
{
    read(n),read(m),read(c),ful=1<<m;
    for(int i=1;i<ful;i++) lb[i]=(i&1)?0:lb[i>>1]+1,cb[i]=cb[i>>1]+(i&1);
    for(int i=1;i<=n;i++) read(a[i]),a[i]--;
    for(int i=2;i<=n;i++) mg[a[i-1]][a[i]]++;
    for(int i=0;i<m;i++)for(int s=1;s<ful;s++)
    {
        mp[s][i]=mp[s^(s&-s)][i]+mg[lb[s]][i];
        mn[i][s]=mn[i][s^(s&-s)]+mg[i][lb[s]];
    }
    memset(dp,0x3f,sizeof(dp)),dp[0]=0;
    for(int s=1,t=s,i,ss,su;s<ful;s++,t=s)
    {
        while(t)
        {
            i=lb[t],t^=(t&-t),ss=s^(1<<i),su=(ful-1)^s;
            dp[s]=min(dp[s],dp[ss]+cb[s]*(mp[ss][i]+c*mn[i][ss]-mn[i][su]+c*mp[su][i]));
        }
    }
    printf("%d\n",dp[ful-1]);
    return 0;
}
}
int main(){return RKK::main();}

稍微（确信）改造一下，让上面预处理出来的连边值随着dp不断更新就能解决空间问题。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long lint;
template<typename TP>inline void read(TP &tar)
{
    TP ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){ret=ret*10+(ch-'0');ch=getchar();}
    tar=ret*f;
}
namespace RKK
{
const int N=23,S=1<<23;
int n,m,c,ful;
int lb[S],cb[S];
int a[100011];
int mn[N][N],mp[N][N],lst[N][N],nw[N];
int dp[S];

int main()
{
    read(n),read(m),read(c),ful=1<<m;
    for(int i=1;i<ful;i++) lb[i]=(i&1)?0:lb[i>>1]+1,cb[i]=cb[i>>1]+(i&1);
    for(int i=1;i<=n;i++) read(a[i]),a[i]--;
    for(int i=2;i<=n;i++)if(a[i]!=a[i-1])
        mn[a[i-1]][a[i]]+=-1,mn[a[i]][a[i-1]]+=c,
        mp[a[i]][a[i-1]]+=1,mp[a[i-1]][a[i]]+=c;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<m;j++) lst[i][j]=mn[i][j]-mp[i][j],nw[i]+=mn[i][j];
        for(int j=1;j<m;j++) lst[i][j]+=lst[i][j-1];
    }
    memset(dp,0x3f,sizeof(dp)),dp[0]=0;
    for(int s=0,t,i;s<ful-1;s++)
    {
        if(s)for(i=0;i<m;i++) nw[i]+=mp[i][lb[s]]-mn[i][lb[s]];
        if(lb[s])for(i=0;i<m;i++) nw[i]+=lst[i][lb[s]-1];
        t=(ful-1)^s;while(t)
        {
            i=lb[t],t^=t&-t;
            dp[s|(1<<i)]=min(dp[s|(1<<i)],dp[s]+nw[i]*cb[s|(1<<i)]);
        }
    }
    printf("%d\n",dp[ful-1]);
    return 0;
}
}
int main(){return RKK::main();}