洛谷 P6622 - 信号传递
chenxia25
2020-07-14 21:54:38
没啥营养的状压DP。
>### [洛谷题目页面传送门](https://www.luogu.com.cn/problem/P6622)
>题意见洛谷。（以下用$s$表示题目中的$k$）
先预处理出$cnt_{i,j}=\sum\limits_{k=1}^{n-1}[S_k=i][S_{k+1}=j]$。然后设位置$i$是$id_i$号信号站，推一波$\sum$算出每个位置对答案的贡献：
$$\begin{aligned}ans&=\sum_{i=1}^m\sum_{j=i+1}^mcnt_{id_i,id_j}(j-i)+\sum_{i=1}^m\sum_{j=1}^{i-1}cnt_{id_i,id_j}s(i+j)\\&=\sum_{i=1}^m-i\sum_{j=i+1}^mcnt_{id_i,id_j}+\sum_{i=1}^mi\sum_{j=1}^{i-1}cnt_{id_j,id_i}+s\sum_{i=1}^mi\sum_{j=1}^{i-1}cnt_{id_i,id_j}+s\sum_{i=1}^mi\sum_{j=i+1}^mcnt_{id_j,id_i}\\&=\sum_{i=1}^mi\left(\sum_{j=i+1}^m\left(s\cdot cnt_{id_j,id_i}-cnt_{id_i,id_j}\right)+\sum_{j=1}^{i-1}\left(s\cdot cnt_{id_i,id_j}+cnt_{id_j,id_i}\right)\right)\end{aligned}$$
然后就有一个很显然的基于位置的状压DP了。设$dp_{i}$表示考虑到第$|i|$位，前$|i|$位的信号站编号集合为$i$时的最小总贡献。边界：$dp_{\varnothing}=0$，目标：$dp_{[1,m]\cap\mathbb Z}$。
令
$$val_{i,j}=\sum_{k\notin j,k\neq i}\left(s\cdot cnt_{id_k,id_i}-cnt_{id_i,id_k}\right)+\sum_{k\in j}\left(s\cdot cnt_{id_i,id_k}+cnt_{id_k,id_i}\right)$$
它可以通过先预处理$\forall i\in[1,m],val_{i,\varnothing}$，剩下的拎出来一个$\mathrm{lowbit}$来$\mathrm O(1)$转移来求出，时间复杂度$\mathrm O(2^mm)$。
那么状态转移方程：
$$dp_{i}=\min_{j\in i}\!\left\{dp_{i-\{j\}}+|i|val_{j,i-\{j\}}\right\}$$
如此，总时空复杂度皆为$\mathrm O(2^mm)$。
至此是我在考场上的做法，$80\mathrm{pts}$，因为空间会爆炸，一个$val$数组大概是$700$多$\mathrm{MB}$。考虑优化。
注意到转移方程里的$val_{j,i-\{j\}}$，不难发现若$x\in y$，那么$val_{x,y}$是不可能被用到的。这样一来，若只存会被用到的，空间立刻减半，能过。可转移性也很显然。实现也很简单，只需要让每个$j$的末$i-1$位原封不动，其他的位拆出来右移$1$位，再拼起来即可。
关于卡空间，还有很多的奇技淫巧可以把空间卡的很小很小，不过研究这个也没啥意义了（
代码（开洛谷自带O2才能过（似乎洛谷机+O2=CCF机？））：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int inf=INT_MAX;
int lowbit(int x){return x&-x;}
const int M=23;
int n,m,s;
int cnt[M][M];
int val[M][1<<M-1];//卡空间
int dp[1<<M];
int main(){
cin>>n>>m>>s;
int las;
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
x--;
if(i>1)cnt[las][x]++;//预处理cnt
las=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];//预处理j=0的情况
for(int j=1;j<1<<m;j++)if(!(j&1<<i)){
int x=j^lowbit(j),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)]);//转移方程
}
}
cout<<dp[(1<<m)-1];
return 0;
}
```