Description

Bsny的書架亂成一團了，幫他一下吧！
他的書架上一共有n本書，我們定義混亂值是連續相同高度書本的段數。例如，如果書的高度是30，30，31，31，32，那么混亂值為3；30，32，32，31的混亂值也為3。但是31，32，31，32，31的混亂值為5，這實在是太亂了。
Bsny想盡可能減少混亂值，但他有點累了，所以他決定最多取出k本書，再隨意將它們放回到書架上。你能幫助他嗎？

Input

第一行兩個整數n，k，分別表示書的數目和可以取出的書本數目。
接下來一行n個整數表示每本書的高度。

Output

僅一行一個整數，表示能夠得到的最小混亂值。

Sample Input

5 1
25 26 25 26 25

Sample Output

3

Data Constraint

20%的數據：1≤n≤20，k=1。
40%的數據：書的高度不是25就是32，高度種類最多2種。
100%的數據：1≤k≤n≤100，注意所有書本高度在 [25,32]。

Solution

• 這題的亮點就是書的高度高度密集，于是敏感地想到狀壓DP

• 先把高度減去24 方便處理，再把書分成高度相同的幾段，記錄段數和每一段的長度

• 設狀態 f[i][j][k][l] 表示，前 i 本書中，抽出了 j 本，沒抽出的書里最后一本的高度是 k ，沒抽出的書狀態是 l ，整體的最小混亂度。

• 那么第一種情況：第 i 本不抽出，轉移顯然；

• 第二種情況：第 i 本抽出，則又分兩種小情況：

• 抽出的書放到前面，則轉移可以通過狀態 l 得到；
• 抽出的書放到后面，則轉移可以通過預處理后面得到。

• 最后數組可以開滾動，總時間復雜度為 O(28?8?N?K)

Code

#include<cstdio> #include<cstring> #define F f[1^roll][j][k][l] using namespace std; const int N=101; int num,roll; int a[N],b[N],c[N],d[N],p[9]; bool bz[N]; int f[2][N][9][1<<8]; inline int read() {int data=0; char ch=0;while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data; } inline void work(int &x,int y){if(x>y) x=y;} int main() {int n=read(),m=read();for(int i=p[0]=1;i<=8;i++) p[i]=p[i-1]*2;for(int i=1;i<=n;i++){a[i]=read()-24;if(a[i]!=a[i-1]) b[++num]=a[i];c[num]++;}for(int i=num;i;i--){if(bz[b[i]]) d[i]++;bz[b[i]]=true;}memset(f[0],60,sizeof(f[0]));f[0][0][0][0]=0;for(int i=1;i<=num;i++){roll=1^roll;memset(f[roll],60,sizeof(f[roll]));for(int j=0;j<=m;j++)for(int k=0;k<9;k++)for(int l=0;l<p[8];l++){if(F>n) continue;work(f[roll][j][b[i]][l|p[b[i]-1]],F+(b[i]!=k));if(j+c[i]>m) continue;work(f[roll][j+c[i]][k][l|p[b[i]-1]],F+!(l&p[b[i]-1]));if(d[i]) work(f[roll][j+c[i]][k][l],F);}}int ans=1e9;for(int j=0;j<=m;j++)for(int k=0;k<9;k++)for(int l=0;l<p[8];l++)work(ans,f[roll][j][k][l]);printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 3853. 【NOIP2014八校联考第2场第2试9.28】帮助Bsny(help)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。