C - Marbles Gym - 102348C

题目链接
题意：给你n个数，可以将相邻的两个交换，问这n个数里面所有相同的数聚到一起的最小操作次数。
题解：我们先大概的想一下这个题的做法，首先这道题虽然可以前后交换，但是任何一种情况下前后交换可以等价，所以我们只需要管前移动即可。很明显，这个题要移动的次数很多，情况也很多，而且我们又应该求出所有的情况后才能找到最小值。首先想到朴素暴力，数据范围$3$$\le$n$\le$$10^5$，范围很大，而如果暴力想要解决这个问题的话时间复杂度要近似于n!所以我们要想到优化暴力，这是我们可以想到的是状态压缩dp。

我们可以想一下最终的状态（假设有123三种颜色），无非就是112233或是221133或是223311或是332211等，是有限的。这里想到状压dp就很明显了，因为状压可以解决这种顺序最优问题。然后呢，数字的范围是20以内，可以状压。

我们在考虑如何状压，由简到难，先大致再细节。我们可以尝试这用顺序最优的问题的解法来解答这道题。顺序最优的话就是通过枚举每一种状态，在当前状态的最优条件下去更新之后的状态，显然这道题仍然可以这样做，我们假设dp[i]是表示i状态下表示的颜色已经摆好的情况下所要花费的最小代价。

然后我们选择如何去状态计算，这里我们更新下面的状态是随意的，可以让下面的一个状态更新到最前面或者最后面或者其他随意一个地方，只要前后保持一致即可，这里因为我们不清楚开始的状态和要更新状态的相对位置,所以我们统一将要更新的状态放到最开始的位置。

下面的任务就是如何计算将此时的更新时所要加的权值，这里我感觉是这道题的关键之处。就是我们更新的时候是每次把需要更新的放到最前面，我们移动的次序不一样需要的权值也就不一样。虽然我们在手算的时候可以自己控制这走到哪一步最优，但是计算机不知道我们的规则，我们必须创建一个规则。创建的那个规则我说不明白，举个样例，尽量看明白：
1 2 1 2 1 3 1 2 3 1
假设我们想要到1 1 1 1 1 2 2 2 3 3这个序列，其实更新的顺序是相反的，先更新3 3 然后 2 2 2 3 3 然后……，我们按照这个顺序呢，实际在移动的时候为了让他移动的步数尽可能少，我们是先将最前面的移动到最前面，然后一次移动，因为这样可以减少没必要的交换，就比如这个样例，我们假设先移动3的话，就会与1发生交换，但是1在后面移动的过程中还要移动到3的前面，还要做一次交换，这样不是最优，所以我们直接先移动最前面的然后一次移动，这样算起来也好算，就是我们只需要计算当前的数前面已经排好的数的数量找出来计算即可，f[i][j]计算数i前面j这个数所贡献的权值即可。

下面是AC代码：

#include
#include
#include
#include
using namespace std;
#define int long long
const int N=4e5+10;
int a[N],b[N],c[N];
int f[25][25],cnt[25];
int dp[5*N],n,m;
signed main()
{
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        ++cnt[a[i]-1];
        for(int j=0; j<20; j++) f[a[i]-1][j]+=cnt[j];//这就是计算权值的过程，好好理解一下，假设1 2 3 2 3 1 1 2 这里1前面2的贡献就是1+1+3=5
    }
    for(int i=0; i<(1<<20); i++)
    {
        for(int j=0; j<20; j++)
        {
            if(((1<<j)&i)!=1)//i的第j位是0,表示可以更新
            {
                int now=dp[i];
                for(int k=0; k<20; k++)
                {
                    if((1<<k)&i)//i的第k位是1
                    {
                        now+=f[k][j];//计算在前面已经出现的有多少个贡献
                    }
                }
                dp[i|(1<<j)]=min(dp[i|(1<<j)],now);//更新权值的过程
            }
        }
    }
    cout<<dp[(1<<20)-1]<<endl;//最终答案的式子，这里可能会有疑问这里20对不对，其实是对的我们可以把原来的答案看作是有20个1，不过其中有些1是上权值是0.
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

总结：这题的状态压缩思维不太难，难得是转移的过程，我们在做题的过程中可以去一步一步分析这个题，可能在找自己想要的答案的过程中就可以发现其中的规律，解决问题。