# Noble 的博客

♡虹蓝♡

### 题解 P6622 【[省选联考 2020 A/B 卷] 信号传递】

posted on 2020-06-23 17:11:03 | under 题解 |

1. x在左侧，提供$-p_x$的代价，在右侧，提供$p_x*k$的代价。

2. y在左侧，提供$p_y*k$的代价，在右侧，提供$p_y$代价。

？？？？？

#include <iostream>
using namespace std;
const int kmaxs=1<<23;
const int kmaxb=13;
const int kmaxbs=1<<kmaxb;
const int kmaxn=24;
const int kmaxm=100000+5;
const int s2b=12;
const int s1b=0;
const int inf=1e9;
int dp[kmaxs+10];
int t1[kmaxbs][kmaxn];
int t2[kmaxbs][kmaxn];
int a[kmaxm];
int cnt[kmaxn][kmaxn];
int valyx[kmaxn][kmaxn];
int valxy[kmaxn][kmaxn];
int pos[kmaxbs];
char hsh[kmaxs];
int n,m;
int K;
int s1,s2;
#define bit(x) (1<<((x)-1))
#define cal_yx(x,y) (valyx[(x)][(y)])
#define cal_xy(x,y) (valxy[(x)][(y)])
/*
int cal_yx(int x,int y)
{
return cnt[y][x]+cnt[x][y]*K;
}
int cal_xy(int x,int y)
{
return cnt[x][y]*-1+cnt[y][x]*K;
}*/
int cal(int s,int x,int ts,int bs)
{
int r=0;
int y=0;
for(int i=1;i<=ts;++i)
{
y=bs+i;
if(x==y)continue;
if(bit(i)&s)//got
{
r+=cal_yx(x,y);
}
else
{
r+=cal_xy(x,y);
}
}
return r;
}
inline int cost2(int x,int s)
{
int st1=s&((1<<s1)-1);
s>>=s1;
int st2=s&((1<<s2)-1);
return t1[st1][x]+t2[st2][x];
}
inline int my_count(int s)
{
int st1=s&((1<<s1)-1);
s>>=s1;
int st2=s&((1<<s2)-1);
return pos[st1]+pos[st2];
}
#define lowbit(x) ((x)&(-(x)))
void solve2()
{
s1=s2b;
s2=n-s1;
int c=0;
for(int s=0;s<(1<<s1);++s)
{
c=0;
for(int k=1;k<=n;++k)
{
if(bit(k)&s)
{
++c;
continue;
}
t1[s][k]=cal(s,k,s1,s1b);
}
pos[s]=c;
}
for(int s=0;s<(1<<s2);++s)
{
for(int k=1;k<=n;++k)
{
if((k>s2b)&&(bit(k-s2b)&s))
continue;
t2[s][k]=cal(s,k,s2,s2b);
}
}
int p=0,i;
for(int s=1;s<(1<<n);++s)
{
dp[s]=inf;
p=my_count(s);
for(int j=s;j;j-=lowbit(j))
{
i=hsh[lowbit(j)];
dp[s]=min(dp[s],dp[s^bit(i)]+(p)*cost2(i,s^bit(i)));
}
}
}
int cost1(int x,int s)
{
int r=0;
for(int y=1;y<=n;++y)
{
if(y==x)continue;
if(s&bit(y))//yx
{
r+=cal_yx(x,y);
}
else
{
r+=cal_xy(x,y);
}
}
return r;
}
void solve1()
{
int p=0;
for(int s=1;s<(1<<n);++s)
{
dp[s]=inf;
p=0;
for(int i=1;i<=n;++i)
{
if(s&bit(i))
++p;
}
for(int i=1;i<=n;++i)
{
if(s&bit(i))
{
dp[s]=min(dp[s],dp[s^bit(i)]+p*cost1(i,s^bit(i)));
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>m>>n>>K;
for(int i=1;i<=m;++i)
{
cin>>a[i];
if(i>1)
cnt[a[i-1]][a[i]]++;
}
for(int x=1;x<=n;++x)
{
hsh[bit(x)]=x;
for(int y=1;y<=n;++y)
{
if(x==y)continue;
valyx[x][y]=cnt[y][x]+cnt[x][y]*K;
valxy[x][y]=(-cnt[x][y])+cnt[y][x]*K;
}
}
if(n<=12)
{
solve1();
}
else
{
solve2();
}
cout<<dp[(1<<n)-1]<<'\n';
return 0;
}

//之前睿智了把题解交到d1t1了，靴靴管理员给移动过来。。。。