[cf 585 E] Marbles

（一道Div2E不会，我太难了）

题意：

给你一个长度为$n$的颜色序列$A$，每次操作可以选择两个相邻元素交换，求把序列交换成“相同颜色挨在一起”所需的最少操作数。

按颜色排序：设颜色$col$在序列中出现的最左处为$l$，最右处为$r$，则$A_{l},\cdots , A_{r}=col$

$n\leq 4\times 10^5,A_{i}\leq 20$

题解：

根据那个20的范围我们可以考虑一个状压dp的做法。

一般人定义状态都是设$dp(s)$表示排好s中的颜色所需要的最少步数，转移时将其他颜色视为空位。

但这样发现还需要记录状态s的位置，才能计算答案。

这道题计算答案的方法比较巧妙，它的状态是$dp(s)$表示当这个序列中只有s中的颜色时将这个序列变得合法所需要的最少步数。

有什么区别？一个是将其他颜色视为空位，一个是直接抹除其他颜色以及它们所在的位置。

为什么要这样？假如在颜色i,j中间有颜色k，那么将j交换到i前面可以分成两种交换，一种是i与j的交换，一种是j与k的交换。

那么此时相当于只计算了前一种交换而忽略了后一种交换，看起来非常错误。

但注意到，若产生这样的情况，那么k在答案中必在i，j之前，此时一定有先将k换到前面再将j换到i前面更优。

也就是说，虽然这个做法在中间过程中答案大概率是错误的，但最终的答案却是正确的。

证明可以考虑从：

(1)得到的答案在原序列中一定可以做到；

(2)得到的答案一定不劣于正确答案；

这两点来证明。

那么我们预处理$cnt(i,j)$表示当序列中只有i,j两种颜色时，将颜色i交换到颜色j前面所需的最少步数。

画个图发现转移时累加的答案为$\sum {cnt(i,k)}$

并不难写，复杂度$O(400\times n)$

（我根本就没学明白dp）

代码：

#include<bits/stdc++.h>

#define maxn 400005

#define maxm 25

#define inf 0x7fffffff

#define ll long long

using namespace std;

int N,M,A[maxn];

ll dp[<<maxm-],cnt[maxm][maxm]; //cnt[i][j]:put i infront j

queue<int> q; bool vis[maxm]; 

inline int read(){

    int x=,f=; char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

int main(){

    N=read(),M=;

    for(int i=;i<=N;i++) A[i]=read();

    for(int x=;x<=M;x++)

        for(int y=;y<=M;y++){

            while(!q.empty()) q.pop();

            for(int i=;i<=N;i++){

                if(A[i]==x){

                    if(q.empty()) continue;

                    int u=q.front();

                    cnt[x][y]+=(ll)q.size();

                    q.pop(),q.push(i);

                }

                else if(A[i]==y) q.push(i);

                else continue;

            }

        }

    memset(dp,,sizeof(dp));

    dp[]=;

    for(int s=;s<(<<M);s++){

        memset(vis,,sizeof(vis));

        for(int i=;i<=M;i++){

            if(s&(<<i-)) vis[i]=;

            else vis[i]=;

        }

        for(int i=;i<=M;i++){

            if(s&(<<i-)) continue;

            ll ans=;

            for(int j=;j<=M;j++)

                if(vis[j]) ans+=cnt[i][j];

            dp[s|(<<i-)]=min(dp[s|(<<i-)],dp[s]+ans);

        }

    }

    printf("%I64d\n",dp[(<<M)-]);

    return ;

}

Marbles

巴特西

[cf 585 E] Marbles

最新文章

热门文章