【题解】珠宝

深碍√TFBOYSˉ_ 2021-11-11 04:01 326阅读 0赞

# 题目大意 #

Elly有一排$n$颗珍珠（$1 \\leq n \\leq 1000$）。每颗珍珠的颜色是$m$种不同的颜色的其中一种（$1 \\leq m \\leq 15$），第$i$颗珍珠的颜色是$a\[i\]$。现在她想让颜色相同的珍珠要排在相邻，最终配置中颜色的顺序并不重要。必须移动的珍珠数量是多少才能按颜色分组？（移动珍珠意味着将它从行中取出然后将其插回任意位置——在任何两个珍珠之间或在所有珍珠之前或之后。）

# 题解 #

因为我们把珍珠取出来后就可以插入任意位置，所以我们可以排好后再插入，也就是我们并不需要管取出后的珍珠，只需要考虑取出哪些珍珠。

我们设$dp\[i\]\[S\]$表示前$i$颗珍珠中，所有珍珠的颜色都在集合$S$内的最少需要取出的珍珠数量。

容易想到。当$a\[i\] \\notin S$时，有

$$dp\[i\]\[S\] = dp\[i - 1\]\[S\] + 1$$

而当$a\[i\] \\in S$时，此时第$i$颗珍珠要么保留，要么也要取出。

如果取出的话，那还是之前的状态转移方程

$$dp\[i\]\[S\] = dp\[i - 1\]\[S\] + 1$$

如果保留的话，那我们要枚举$j \\in \[1,i\]$，在$\[1,j)$的范围内集合为$S - S\_\{a\[i\]\}$的情况，这里已经用$dp\[j - 1\]\[S - S\_\{a\[i\]\}\]$记录了；在$\[j,i\]$的范围内集合仍为$S$。

当$a\[i\] \\not = a\[j\]$时，显然第$j$颗珍珠要取出。这里我们用$Count(j,i)$，表示$\[j,i\]$中要取出的珍珠数量。

当$a\[i\] = a\[j\]$时，则有状态转移方程

$$dp\[i\]\[S\] = dp\[j - 1\]\[S - S\_\{a\[i\]\}\] + Count(j, i)$$

综合两种情况，可以得到最终的状态转移方程为

$$dp\[i\]\[S\] = \\left \\\{ \\begin\{matrix\} dp\[i - 1\]\[S\] + 1, a\[i\] \\notin S \\\\ \\min \\\{dp\[i - 1\]\[S\] + 1, \\underset\{1 \\leq j \\leq i\}\{\\min\} \\\{ dp\[j - 1\]\[S - S\_\{a\[i\]\}\] + Count(j, i) \\\} \\\},a\[i\] \\in S \\end\{matrix\} \\right.$$

此时的时间复杂度为$O(2^\{m\} n^\{2\})$，还是TLE。

实际上我们只需要记录有关$j$部分的前缀最小值，就能省去枚举$j$的循环，时间复杂度降为$O(2^\{m\}n)$，具体细节看下面的代码。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstring>
    
    #define MAX_N (50 + 5)
    #define MAX_M (15 + 5)
    #define MAX_S ((1 << 15) + 5) 
    
    using namespace std;
    
    int n, m;
    int a[MAX_N];
    int sum[MAX_M][MAX_N];
    int dp[MAX_N][MAX_S], mdp[MAX_M][MAX_S], l[MAX_M][MAX_S];
    
    int main()
    {
        cin >> n >> m;
        for(int i = 1; i <= n; ++i)
        {
            cin >> a[i];
        }
        memset(dp, 0x3f, sizeof dp);
        memset(mdp, 0x3f, sizeof mdp);
        const int lim = (1 << m) - 1;
        for(int c = 1; c <= m; ++c)
        {
            for(int i = 1; i <= n; ++i)
            {
                sum[c][i] = sum[c][i - 1];
                if(a[i] != c) ++sum[c][i];
            }
        }
        for(int s = 0; s <= lim; ++s)
        {
            dp[0][s] = 0;
        }
        for(int i = 1; i <= n; ++i)
        {
            dp[i][0] = i;
        }
        int p;
        for(int s = 1; s <= lim; ++s)
        {
            for(int i = 1; i <= n; ++i)
            {
                p = 1 << a[i] - 1; 
                dp[i][s] = dp[i - 1][s] + 1;
                if(s & p)
                {
                    mdp[a[i]][s] = min(mdp[a[i]][s] + sum[a[i]][i] - sum[a[i]][l[a[i]][s]], dp[i - 1][s - p]);
                    dp[i][s] = min(dp[i][s], mdp[a[i]][s]);
                    l[a[i]][s] = i;
                }
            }
        }
        cout << dp[n][lim]; 
        return 0;
    }

参考程序

**毒瘤区赛，毒瘤出题人**

转载于:https://www.cnblogs.com/kcn999/p/11276808.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/a1c7e0249c4d4a759a625353da85b45c.png