洛谷 P6622 - 信号传递

· · 题解

没啥营养的状压DP。

洛谷题目页面传送门

题意见洛谷。（以下用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机？））：

#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;
}