[Luogu]P3694 邦邦的大合唱战队
本文最后更新于 292 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/lp3694/

题意

题目传送门

$N$ 个人,分别属于 $M$ 个组,要求同组的人站在一起。
每个人可以出队,出队后留出空位,出队后的人可以在任意空位归队。
求最少出队人数。

解法

看到 $M$ 的数据范围极小,猜测可能是状压DP
但没有想出来到底是如何状压,于是重新审视题意。

全排列

可以发现,最后同组的人站在一起,一定会形成组的顺序,例如:

111111,222222,333333
222222,111111,333333
333333,111111,222222
….

类似如此,那么可以全排列枚举组的顺序。
而确定组的顺序后,每个组的范围就确定下来了。
而对于每个人,如果他的位置恰好属于他组的范围,他便不用出队,否则他一定要出队。
依次检验,取最小值,即可得到答案。
复杂度为 $O(NM!)$,只能通过四个点。

考虑进行优化,可以发现这个 $O(N)$ 能够用预处理前缀和的方式去掉。
维护 $s_{i,j}$ 代表前 $i$ 人中属于 $j$ 组的人数,即可用 $O(1)$ 的时间计算出一组的范围内应有多少人出队。
复杂度降低到 $O(M!)$,可以通过七个点。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
template<typename T>void read(T &r){static char c;r=0;for(c=getchar();c>'9'||c<'0';c=getchar());for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());}
const int maxn = 1e5 + 10;
const int maxm = 21;
int n,m;
int a[maxn];
int num[maxm];
int order[maxm];
int s[maxn][maxm];
int main()
{
    read(n);
    read(m);
    for(int i = 1;i<=n;++i)
        read(a[i]),num[a[i]]++,s[i][a[i]]++;
    for(int i = 1;i<=n;++i)
        for(int j = 1;j<=m;++j)
            s[i][j] += s[i-1][j];
    for(int i = 1;i<=m;++i)
        order[i] = i;
    int ans = 1 << 30;
    do
    {
        int res = 0;
        int l = 0,r = 0;
        for(int i = 1;i<=m;++i)
        {
            l = r + 1;
            r = l + num[order[i]] - 1;
            res += num[i] - (s[r][order[i]] - s[l-1][order[i]]);
        }
        ans = min(ans,res);
    } while (next_permutation(order + 1, order + 1 + m));
    printf("%d",ans);
    return 0;
}

状压DP

想要将 $O(M!)$ 的复杂度降低到 $O(2^M)$,使用状压DP的方法。
有数据范围的提示,很容易定义出状态:
状态 $S$ 每位代表该组是否已处理完成。
如何转移呢?可以枚举排在最后的组。
计算出当前队列的长度,枚举排在最后的组,已知排在最后组的长度,即可确定排在最后组的范围。
确定组范围后,即可计算出该范围内应有多少人出队。
枚举当前状态每个可能的最后组,取最小值进行转移。

dp[status] = min(dp[status],dp[status ^ (1<<(i-1))] + num[i] - (s[r][i] - s[l-1][i]));

实质上,这个状压DP也是在枚举顺序。
不同于全排列,状压转移时并不知道子状态中的顺序,只知道子状态已完成的组,而将当前组加在子状态队列最后。
或许借此剪去了部分无用的枚举。

笔者使用了记忆化搜索的写法,预处理了每个状态的队列长度。

#include <cstdio>
#include <cstring>
using namespace std;
template<typename T>
inline T min(const T &a,const T &b){return a<b?a:b;}
template<typename T>
void read(T &r){static char c;r=0;for(c=getchar();c>'9'||c<'0';c=getchar());for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());}
const int maxn = 1e5 + 10;
const int maxm = 21;
int n,m;
int a[maxn];
int num[maxm];
int s[maxn][maxm];
int len[1<<maxm];
int dp[1<<maxm];
int dfs(int status)
{
    if(dp[status] != 1<<30)
        return dp[status];
    for (int i = 1; i <= m; ++i)
        if(status & (1<<(i-1)))
        {
            int l = len[status] - num[i] + 1,r = len[status];
            dp[status] = min(dp[status],dfs(status ^ (1<<(i-1))) + num[i] - (s[r][i] - s[l-1][i]));
        }
    return dp[status];
}
int main()
{
    read(n);
    read(m);
    for(int i = 1;i<=n;++i)
        read(a[i]),num[a[i]]++,s[i][a[i]]++;
    for(int i = 1;i<=n;++i)
        for(int j = 1;j<=m;++j)
            s[i][j] += s[i-1][j];
    int maxs = (1<<m) - 1;
    for(int i = 1;i<=maxs;++i)
        dp[i] = 1<<30;
    for(int i = 1;i<=maxs;++i)
        for(int j = 1;j<=m;++j)
            if(i & (1<<(j-1)))
                len[i] += num[j];
    printf("%d",dfs((1<<m)-1));
    return 0;
}
本文标题:[Luogu]P3694 邦邦的大合唱战队
本文作者:Clouder
本文链接: https://www.codein.icu/lp3694/
转载请标明。

评论

  1. 龙王
    10月前
    2020-4-09 2:26:54

    宝贝儿写的真好,龙王爱你哦

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇