「联合省选 2020 A | B」信号传递

数据范围很状压。

设 \(f_{sta}\) 表示 \(sta\) 为已放信号站集合时最小的代价。

若能求出 $g_i(sta) $ 表示在 \(sta\) 的状态下放 \(i\) 的代价的系数（即其放的位置的系数），那么我们就可以在 \(O(m\times2^m)\) 的复杂度内使用 dp 解决问题。

注意到 \(g_i(sta)\) 可以在 \(O(m^2\times 2^m)\) 的复杂度内轻易求出。

设 \(L_i(j)\) 表示满足 \(S_i=i\) 且 \(S_{i-1}=j\) 的个数，\(R_i(j)\) 表示 \(S_i=i\) 且 \(S_{i+1}=j\) 的个数。

枚举 \(i,sta\) 以及 \(j,k\)，那么有：

\[g_i(sta)=\sum_j{L_i(j)\times K-R_i(j)}+\sum_k{L_i(k)+R_i(k)\times K} \]

其中 \(j\in sta,k\not\in sta\)。

瓶颈在于求解 \(g\) 数组。

注意到 \(g\) 数组是可以递推的。

\[g_i(sta\cup\{x\})=g_i(sta)+L_i(x)\times(1-K)+R_i(x)\times(1+K) \]

这样我们在 \(O(m\times2^m)\) 的时间内处理出来了 \(g\) 数组，但是我们会爆空间，得优化空间。

我们考虑一个结论：

二进制从 \(0\) 数到 \(n\)，所有比特位变化的总次数为 \(2n\)。

证明：第 \(0\) 位每增加 \(1\) 变一次，第 \(1\) 位每增加 \(2\) 变一次，以此类推，第 \(i\) 位每增加 \(2^i\) 变一次。

那么总变化次数就是：

\[n\sum_i\dfrac{1}{2^i}=2n \]

所以我们可以将 \(g\) 数组 \(sta\) 那维滚掉，在 dp 的时候随着 sta 的增加暴力更新 \(g_i\) 即可。

总复杂度 \(O(m\times2^m)\)。

代码如下：

#include
#define lowbit(i) (i&(-i))
using namespace std;
const int MAXN = 1e5+5;
bool Small;
int n,m,K,S[MAXN],f[1<<23],g[23],c[23][23],L[23][23],R[23][23];
int lg[(1<<23)];
bool Sunny;
int main()
{
//	cout<<1.0*(&Sunny-&Small)/1024/1024<<"MB"<>1]+1;
	
	for(int i=1;i<=n;++i) scanf("%d",&S[i]);
	
	for(int i=1;i