帮助Bsny 题目描述 Bsny的书架乱成一团了，帮他一下吧！
他的书架上一共有n本书，我们定义混乱值是连续相同高度书本的段数。例如，如果书的高度是30，30，31，31，32，那么混乱值为3；30，32，32，31的混乱值也为3。但是31，32，31，32，31的混乱值为5，这实在是太乱了。
Bsny想尽可能减少混乱值，但他有点累了，所以他决定最多取出k本书，再随意将它们放回到书架上。你能帮助他吗？
输入 第一行两个整数n，k，分别表示书的数目和可以取出的书本数目。
接下来一行n个整数表示每本书的高度。
输出 仅一行一个整数，表示能够得到的最小混乱值。
样例输入 5 1 25 26 25 26 25 样例输出 3 提示 20%的数据：1≤n≤20，k=1。
40%的数据：书的高度不是25就是32，高度种类最多2种。
100%的数据：1≤k≤n≤100，注意所有书本高度在[25,32]。
此题是四维动规 考试时只想着三维，死活不能转移出来 f[i][j][l][p]表示 前i本书 拿出了j本 剩下的书的最后一个高度是l 剩下的书出现过的高度为p(一个二进制状态) f[i][j][l][p]向后转移,转移太长懒得写了，自己悟 然后在最后，统计下全部被拿出的书的种类，放回时混乱度加1 #include<iostream> #include<cstdio> using namespace std; bool flag[10]; int a[105],tot[300]; int f[105][105][10][300]; int main(){ int n,k; scanf("%d%d",&n,&k); for (int i=1;i<=8;++i) flag[i]=false; int nn=0; for (int i=1;i<=n;++i){ scanf("%d",&a[i]); a[i]-=24; if (flag[a[i]]==false) ++nn; flag[a[i]]=true; } //cout<<nn<<endl; tot[0]=0; for (int i=1;i<256;++i) tot[i]=tot[i-(i&(-i))]+1; for (int i=0;i<=n;++i) for (int j=0;j<=k;++j) for (int l=0;l<=8;++l) for (int p=0;p<256;++p) f[i][j][l][p]=1<<29; f[0][0][0][0]=0; for (int i=0;i<n;++i) for (int j=0;j<=k;++j) for (int l=0;l<=8;++l) for (int p=0;p<256;++p) if (f[i][j][l][p]!=1<<29){ if (a[i+1]==l){ f[i+1][j][l][p]=min(f[i+1][j][l][p],f[i][j][l][p]); f[i+1][j+1][l][p]=min(f[i+1][j+1][l][p],f[i][j][l][p]); }else{ f[i+1][j][a[i+1]][p|(1<<(a[i+1]-1))]=min(f[i+1][j][a[i+1]][p|(1<<(a[i+1]-1))],f[i][j][l][p]+1); f[i+1][j+1][l][p]=min(f[i+1][j+1][l][p],f[i][j][l][p]); } //cout<<i<<" "<<j<<" "<<l<<" "<<p<<" : "<<f[i][j][l][p]+nn-tot[p]<<endl; } int ans=1<<29; //for (int i=0;i<10;++i) cout<<i<<" "<<tot[i]<<endl; for (int i=0;i<=8;++i) for (int j=0;j<256;++j){ ans=min(ans,f[n][k][i][j]+nn-tot[j]); //cout<<f[n][k][i][j]<<endl; } printf("%d\n",ans); return 0; }