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

tanghg

5个月前发布

题目大意

详细题目传送门
给出 \(n,m,k\) 和一个长度为 \(n\) 的序列 \(S\)，其中 \(S_i\in [1,m]\)。

对于一个 \(x\rightarrow y\) 的代价 \(f(x,y)\)，有：

\[ \left\{ \begin{aligned} y-x &&x\leq y\\ kx+ky &&x>y\\ \end{aligned} \right.\]

你需要求一个长度为 \(m\) 排列 \(P\),使 \(\sum_{i=1}^{n-1}f(P_{S_i},P_{S_i+1})\) 最小。

\(n\leq 10^5,m\leq 23,k\leq 100\)

思路

发现 \(m\) 很小，所以看起来就很像一些状压动归。但是发现即使是枚举 \(P\) 的暴力要求一个总代价也是 \(O(n\cdot m!)\) 的，所以希望将它转成一个只关于 \(m\) 的形式。

这个时候可以拆贡献，发现对于 \(S_i\) 的贡献只与 \(S_i+1\) 有关。这个时候我们可以记 \(C(x,y)\) 表示 \(S\) 中有多少 \((S_i=x,S_{i+1}=y)\)。这样我们在算 \(P\) 的代价时就可以枚举 \(x,y\in[1,m]\)，然后加贡献

\[C(x,y)\cdot\left\{ \begin{aligned} P_y-P_x &&P_x\leq P_y\\ kP_x+kP_y &&P_x>P_y\\ \end{aligned} \right.\]

这样就优化到了 \(O(m^2m!)\)，我们的时间复杂度已与 \(n\) 无关。

然后考虑状压动规。如果先考虑 \(F_s\) 表示现在 \([1,|s|]\) 的数分别填在了 \(s\) 为 \(1\) 的位置上，但是无法转移，因为不知道具体是哪些值的话 \(C(x,y)\) 就是无法更新的。

但是可以有转移 \(F_s\) 表示现在填了前 \(|s|\) 个位置，填了 \(s\) 中的这些数。发现就可以转移，因为我们只关心大小关系，那么还没有出现的肯定在之后，那么转移时的大小关系就可以确定了。

那么转移一个 \(i\) 时考虑到 \(j\) 有几种情况：

若 \(i\rightarrow j\)， \(j\in s\)，\(P_j<P_i\)，所以有贡献 \(C(i,j)\cdot kP_i\)
若 \(i\rightarrow j\)， \(j\notin s\)，\(P_j>P_i\)，所以有贡献 \(C(i,j)\cdot (-P_i)\)
若 \(j\rightarrow i\)， \(j\in s\)，\(P_j<P_i\)，所以有贡献 \(C(j,i)\cdot P_i\)
若 \(j\rightarrow i\)， \(j\notin s\)，\(P_j>P_i\)，所以有贡献 \(C(j,i)\cdot kP_i\)

那么可以转移

\[G(s,i)=\sum_{j\in s}(C(i,j)\cdot k+C(j,i))+\sum_{j\notin s}(-C(i,j)+C(j,i)\cdot k) \]

\[F_{s\cup i}\leftarrow F_s+P_iG(s,i) \]

其中按照定义 \(P_i=|s|+1\)。

那么现在的时间复杂度是 \(O(2^mm^2)\) 的，已经有 \(80\) 分了。发现能不能先预处理出 \(G(s,i)\)。发现 \(G(s,i)\) 可以从任何一个大小为 \(|s|-1\) 的子集转移过来。那么可以不妨从去掉最低位 \(1\)（即 lowbit，不妨设位置为 \(j\)）的位置 \(s^{‘}\) 转移。

\[G(s,i)=G(s^{‘},i)+C(i,j)\cdot k+C(j,i)-(-C(i,j)+C(j,i)\cdot k) \]

\[=G(s^{‘},i)+C(i,j)\cdot (k+1)+C(j,i)\cdot (1-k) \]

现在我们已经做到了时空都是 \(O(2^mm)\) 了，但是发现空间不够大。但是发现所有的 \(G(s,i),i\in s\) 都是没有意义的，所以我们可以只保存 \(2^{m-1}\) 个 \(G\)，虽然实现麻烦但是可以优化到空间 \(O(2^{m-1}m)\),时间 \(O(2^mm)\) 可以通过本题。

代码

#include<bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(register ll i=(a);i<=(b);++i)
using namespace std;
typedef int ll;
const ll MAXN=1e5+5;
const ll MAXM=23;
const ll MAXLM=(1<<23)+2;
ll n,m,k,a[MAXN],cnt[MAXM][MAXM];
namespace Task3{
    ll f[MAXLM],bt1[MAXLM],lg[MAXLM];
    ll v[MAXLM/2][MAXM];
    ll gb(ll x){
        ll ans=0;
        while(x){
            ans+=(x&1);
            x>>=1;
        }
        return ans;
    }
    void Do(){
        memset(f,0x3f,sizeof(f));
        f[0]=0;
        rep(i,0,(1<<(m))){
            bt1[i]=gb(i);
        }
        rep(i,2,(1<<m)){
            lg[i]=lg[i>>1]+1;
        }
        rep(i,0,m-1){
            rep(j,0,m-1){
                if(i!=j){
                    v[0][i]+=k*cnt[j][i]-cnt[i][j];
                }
            }
        }
        rep(i,0,m-1){
            rep(j,1,(1<<(m-1))-1){
                ll lb=(j&(-j)),pc=lg[lb]+(lg[lb]>=i);
                v[j][i]=v[j^lb][i]+cnt[i][pc]*(k+1)+cnt[pc][i]*(1-k);
            }
        }
        rep(S,1,(1<<m)-1){
            rep(i,0,m-1){
                if((S&(1<<i))){
                    ll ns=S^(1<<i);
                    ll val=f[ns]+(bt1[ns]+1)*v[(ns&((1<<i)-1))|((ns>>(i+1))<<i)][i];
                    f[S]=min(f[S],val);
                }
            }
        }
        cout<<f[(1<<m)-1]<<endl;
    }
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	rep(i,1,n){
		cin>>a[i];
        a[i]--;
	}
    rep(i,1,n-1){
        cnt[a[i]][a[i+1]]++;
    }
	Task3::Do();
	return 0;
}

来源链接：https://www.cnblogs.com/tanghg/p/18744473/solution-p6622

评分

欢迎为Ta评分