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

duyi · 2020-06-28 10:25:51 · 题解

更好的阅读体验

强烈推荐更好的的阅读体验↑

题目链接

初步转化

按题意，我们暴力枚举这m个信号站的排列顺序，时间复杂度O((m!)\cdot n)。

容易发现，题目给出的这个长度为n的序列S具体是什么不重要，重要的是，每一对信号站i,j，在S里作为相邻的位置，出现了多少次。也就是有多少个位置p (1\leq p<n)满足S_p=i,S_{p+1}=j。我们记这个数量为\text{cnt}[i][j]。

对于任意i\neq j，\text{cnt}[i][j]就表示要从信号站i，向信号站j，进行多少次传递。设两个信号站的位置，分别为\text{pos}[i],\text{pos}[j]，则它们会对答案产生的代价就是：

\begin{cases} \text{pos}[j]-\text{pos}[i]&&(\text{pos}[i]<\text{pos}[j])\\ k\cdot(\text{pos}[i]+\text{pos}[j])&&(\text{pos[i]}>\text{pos}[j]) \end{cases}

做了这步转化后，如果还是暴力枚举这m个信号站的排列顺序，时间复杂度优化为O(n+(m!)\cdot m^2)。至此我们复杂度的瓶颈与n无关了。

朴素DP

接下来，结合m的大小，容易想到状压DP。此处就有两种状态设计的思路：

设dp[s]表示考虑了前|s|个数，放在了s里的这些位置上。
设dp[s]表示考虑了前|s|个位置，填了s里的这些数。

发现，第一种状态设计是无法转移的。所以我们选择第二种。事实上，考试时我就一直在想第一种，把自己搞自闭了。其实，按位置考虑、按数值考虑，这都是常见的方法，所以要学会灵活变通，一个不行就想想另一个。

我们选择了第二种状态设计：设dp[s]表示考虑了前|s|个位置，填了s里的这些数。

那考虑转移。首先要枚举在新加入的位置，也就是在第\text{pos}=|s|+1个位置，填哪个数。假设我们填i。考虑填i会新增哪些代价。它会分别和：前面的数（也就是s里的数）、后面的数（也就是不在s里，但也不等于i的数）产生代价。而且每种代价都有两个方向。具体来说：

对于一个前面的数j，从i到j产生的代价是：\text{pos}\cdot k\cdot \text{cnt}[i][j]。
对于一个前面的数j，从j到i产生的代价是：\text{pos}\cdot\text{cnt}[j][i]。
对于一个后面的数j，从i到j产生的代价是：-\text{pos}\cdot \text{cnt}[i][j]。
对于一个后面的数j，从j到i产生的代价是：\text{pos}\cdot k\cdot \text{cnt}[j][i]。

所以我们也可以写出式子：

dp[s+i]\leftarrow dp[s]+\text{pos}\cdot \sum_{j\in s}(k\cdot\text{cnt}[i][j]+\text{cnt}[j][i])+\text{pos}\cdot\sum_{j\notin(s+i)}(-\text{cnt}[i][j]+k\cdot \text{cnt}[j][i])

如果枚举i，再枚举j，DP的时间复杂度O(2^mm^2)。期望得70分。

优化时间

我们继续优化。考虑只枚举i。把\text{pos}前的系数（也就是所有j的贡献之和），预处理出来，不妨记为：\text{cost}(s,i)。那么上述的转移式，也可以改写为：dp[s+i]\leftarrow dp[s]+\text{pos}\cdot \text{cost}(s,i)。

考虑预处理\text{cost}(s,i)。首先，根据定义，i\notin s。

我们考虑，\text{cost}(s,i)，可以从“s去掉某个数”的状态，转移过来。我们不妨就去掉j=\text{lowbit}(s)（也就是二进制下最低的，为1的位）。那么，\text{cost}(s,i)=\text{cost}(s-j,i)+(k\cdot \text{cnt}[i][j]+\text{cnt}[j][i])-(-\text{cnt}[i][j]+k\cdot \text{cnt}[j][i])。

这样转移是O(1)的。所以预处理的时间复杂度为O(2^mm)，DP的时间复杂度也降为O(2^mm)。总时间复杂度O(n+2^mm)。但是\text{cost}数组会占用O(2^mm)的空间，这无法承受。所以还要继续优化空间。

优化空间

这题优化空间的方法很多。我讲一种比较好想的。想了解更多方法，可以阅读这篇文章。

发现\text{cost}和\text{dp}的转移，都是按集合从小到大进行的。所以我们就不妨一边DP，一边求\text{cost}。

对每个s，我们把\text{cost}(s,\dots)视为一个大小为m的数组。当前的s，我们先做DP转移，再拿\text{cost}(s\dots)数组去更新所有\text{cost}(s'\dots )。发现更新完之后，\text{cost}(s,\dots)这个大小为m的数组，就可以不要了！

如果能及时地把\text{cost}(s,\dots)这个数组，以某种方式“删除”掉（不再占用空间）。那么，在整个DP的过程中，同一时刻，我们存储的最多只有两种大小的s。因为\text{cost}(s,\dots)只会转移到比它恰好大1的s'。那么空间的极限，就是{23\choose 12}+{23\choose 11}个大小为m的数组，约等于237\text{MB}，完全可以了。

那么怎么实现这个“删除”呢？一种方法是用滚动数组。按大小枚举所有集合。每处理完一种大小，就把数组“滚一次”。另一种方法，是直接利用\texttt{stl}里的\texttt{queue}，向BFS一样，每次取出队首的s，\texttt{pop}掉就行。

空间复杂度，\displaystyle O\left(2^m+m\cdot{m\choose\frac{m}{2}}\right)。前面分析过，大约237\text{MB}，可以通过本题。

参考代码（在LOJ查看）：

//problem:LOJ3302
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

inline void ckmin(int& x,int y){x=(x<y?x:y);}

const int MAXN=1e5,MAXM=23;
const int INF=1e9;
int n,m,K,arr[MAXN+5],cnt[MAXM][MAXM];
int id[1<<MAXM],bitcnt[1<<MAXM];
int dp[1<<MAXM];

struct State{
    int s;
    int v[MAXM];
};

int main() {
    //freopen("transfer.in","r",stdin);
    //freopen("transfer.out","w",stdout);
    cin>>n>>m>>K;
    for(int i=1;i<=n;++i){
        cin>>arr[i];
        arr[i]--;
    }
    for(int i=1;i<n;++i){
        cnt[arr[i]][arr[i+1]]++;
    }

    queue<State>q;
    State s;
    s.s=0;
    for(int i=0;i<m;++i){
        s.v[i]=0;
        for(int j=0;j<m;++j)if(j!=i){
            s.v[i]-=cnt[i][j];
            s.v[i]+=K*cnt[j][i];
        }
    }
    q.push(s);

    int S=(1<<m)-1;
    for(int i=0;i<m;++i)id[1<<i]=i;
    for(int i=1;i<=S;++i){
        bitcnt[i]=bitcnt[i>>1]+(i&1);
        dp[i]=INF;
    }
    while(!q.empty()){
        State curs=q.front();q.pop();
        assert(dp[curs.s]<INF);
        int p=bitcnt[curs.s]+1;
        for(int t=S^curs.s;t;t-=(t&(-t))){
            //枚举curs.s的补集里的一个点i
            int i=id[t&(-t)];
            int new_dp=dp[curs.s];
            int new_s=(curs.s|(1<<i));
            new_dp+=p*curs.v[i];

            ckmin(dp[new_s],new_dp);
        }
        for(int i=0;i<m;++i){
            if((curs.s>>i)&1)break;
            State new_state;
            new_state.s=(curs.s|(1<<i));
            for(int t=S^new_state.s;t;t-=(t&(-t))){
                //枚举new_state.s的补集里的一个点j 
                int j=id[t&(-t)];
                new_state.v[j]=curs.v[j]
                    +(K*cnt[j][i]+cnt[i][j])
                    -(-cnt[j][i]+K*cnt[i][j]);
            }
            q.push(new_state);
        }
    }
    cout<<dp[S]<<endl;
    return 0;
}