題目背景

BanG Dream!里的所有偶像樂隊要一起大合唱，不過在排隊上出了一些問題。

題目描述

N個偶像排成一列，他們來自M個不同的樂隊。每個團隊至少有一個偶像。

現(xiàn)在要求重新安排隊列，使來自同一樂隊的偶像連續(xù)的站在一起。重新安排的辦法是，讓若干偶像出列（剩下的偶像不動），然后讓出列的偶像一個個歸隊到原來的空位，歸隊的位置任意。

請問最少讓多少偶像出列？

輸入輸出格式

輸入格式：

第一行2個整數(shù)N，M。

接下來N個行，每行一個整數(shù)a_i(1\le a_i \le M)a?i??(1≤a?i??≤M)，表示隊列中第i個偶像的團隊編號。

?

輸出格式：

一個整數(shù)，表示答案

?

輸入輸出樣例

輸入樣例#1：
12 4 1 3 2 4 2 1 2 3 1 1 3 4 輸出樣例#1：
7

說明

【樣例解釋】

1 3 √ 3 3 2 3 √ 4 4 2 4 √ 1 2 √ 2 2 3 2 √ 1 1 1 1 3 1 √ 4 1 √

【數(shù)據(jù)規(guī)模】

對于20%的數(shù)據(jù)，N≤20,M=2

對于40%的數(shù)據(jù)，N≤100,M≤4

對于70%的數(shù)據(jù)，N≤2000,M≤10

對于全部數(shù)據(jù)，1≤N≤10^?5??,M≤20

?

這竟然是一道簽到題，我覺得自己可以滾回普及組了。

反過來考慮，要讓最少的人出列就是讓最多的人不出列（留下）。

看m數(shù)據(jù)范圍就是狀壓dp。然后n。。發(fā)現(xiàn)n挺大的，如果能讓最后主算法復(fù)雜度不帶n是最好的，反正復(fù)雜度不能讓n和(1<<m)相乘

我們預(yù)處理出tot[i][j]表示前i個人中，團隊序號為j的人有多少個，復(fù)雜度O(nm)。

然后枚舉每個狀態(tài)，看看這個狀態(tài)可以轉(zhuǎn)移到那些狀態(tài)。

用dp[i]表示第i個狀態(tài)（如果 j 滿足 (1<<(j-1)) & i != 0，則表示j這個團隊的人全都排好了，而且位置在靠前的位置）可以留下的最多人數(shù)，然后就可以dp了。

for(int i=0;i<(1<<m);++i) {sum=0;for(int j=1;j<=m;++j) if(i&(1<<(j-1))) sum+=tot[n][j];l=sum;for(int j=1;j<=m;++j) {if(i&(1<<(j-1))) continue;r=sum+tot[n][j];dp[i|(1<<(j-1))]=max(dp[i|(1<<(j-1))],dp[i]+tot[r][j]-tot[l][j]);}ans=max(ans,dp[i]); }

　　

//Serene #include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> using namespace std; const int maxn=1e5+10,maxm=20,maxmi=1<<20; int n,m,a[maxn],tot[maxn][maxm],dp[maxmi],ans;int aa;char cc; int read() {aa=0;cc=getchar();while(cc<'0'||cc>'9') cc=getchar();while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();return aa; }int main() {n=read();m=read();for(int i=1;i<=n;++i) {a[i]=read();for(int j=1;j<=m;++j) tot[i][j]=tot[i-1][j];tot[i][a[i]]++;}int sum,l,r;for(int i=0;i<(1<<m);++i) {sum=0;for(int j=1;j<=m;++j) if(i&(1<<(j-1))) sum+=tot[n][j];l=sum;for(int j=1;j<=m;++j) {if(i&(1<<(j-1))) continue;r=sum+tot[n][j];dp[i|(1<<(j-1))]=max(dp[i|(1<<(j-1))],dp[i]+tot[r][j]-tot[l][j]);}ans=max(ans,dp[i]);}printf("%d",n-ans);return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/Serene-shixinyi/p/7475529.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P3694 邦邦的大合唱的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。