题解 P6622 【[省选联考 2020 A/B 卷] 信号传递】
_虹_
2020-06-23 17:11:03
一道奇特的状压dp。
分享一个$O(m^22^{m/2+1}+m2^m)$的做法。
首先m<=23，考虑做状压dp。
对于x前往y：
1. x在左侧，提供$-p_x$的代价，在右侧，提供$p_x*k$的代价。
2. y在左侧，提供$p_y*k$的代价，在右侧，提供$p_y$代价。
可以发现，每种移动中，两端点提供的代价只和方向和端点位置有关，与距离无关。对于点x，贡献为$p_x*(-1*a+1*b+k*c)$，abc为三类代价产生次数
显然的，有朴素dp：f(i,s)表示放了前i个位置，放置集合为s。转移为(i,s)=min(f(i-1,s^bit(x)+cost(x,s^bit(x)*i)(bit(x)&s!=0)。时间复杂度$O(m^32^m)$
依靠想象力，我们可以意识到，对于某一点x，其他点之间的位置关系不影响x产生的代价。
我们考虑预处理节点x与所有s产生的贡献，令cost函数变为常数时间。
那么我们有预处理$O(m^22^m)$，dp$O(m^22^m)$.
然后你算一下就发现他卡内存，你根本开不下$m2^m$的数组（dp你可以滚动数组）。
？？？？？
那么我们退而求其次，考虑分组预处理，设每组有k个节点，则有t=m/k（上取整）组。
我们有预处理$O(tm^22^k)$+dp$O(tm^22^m)$，
显然复杂度瓶颈是dp，那么t取2最佳，此时k取12。
这也不行啊这不是连20都跑不过去吗？
~~努力全部木大~~ 不要停下来啊。
每次转移已经非常优秀($O(m)$)，考虑优化dp状态数。
显然大量的状态是冗余的，只有那些i==count(s)的状态才有意义。
那我们可以直接去掉i这一维，因为他其实可以被s表达出来。
那我们有转移方程f(s)=min(f(s^bit(x)+cost(x,s^bit(x)*count(s))(bit(x)&s!=0).
时间复杂度为$O(tm2^m)==O(m2^{m+1})$，预处理count(s)可以卡常，方法同预处理cost。
对于x不属于s，我们考虑跳过x。
预处理2^i对应的i，对于枚举的状态s，直接lowbit后查表得到对应的i；
我们有复杂度$O(tm\sum\limits_{s=1}^{2^m}count(s))$.
即$O(tm2^{m-1})==O(m2^m)$
考场降智想到最后的优化没算清楚就没有写。
放一个$O(m2^m)$代码（其实和$O(m2^{m+1})$就差几行）
```cpp
#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;
}
```
在luogu上不吸氧也只能跑80，但吸氧之后最慢点0.6s。。。
可能是写丑了常数太大。
//之前睿智了把题解交到d1t1了，靴靴管理员给移动过来。。。。