Description

Bsny的书架乱成一团了，帮他一下吧！
他的书架上一共有n本书，我们定义混乱值是连续相同高度书本的段数。例如，如果书的高度是30，30，31，31，32，那么混乱值为3；30，32，32，31的混乱值也为3。但是31，32，31，32，31的混乱值为5，这实在是太乱了。
Bsny想尽可能减少混乱值，但他有点累了，所以他决定最多取出k本书，再随意将它们放回到书架上。你能帮助他吗？

n<=100

Solution

我们发现，书本的高度种类很少，只有8种，这启示我们用二进制来做，
设DP： fi,j,k,l 表示做到了第i本，取出了j本书，i之前（含）出现了的种类（二进制压缩），当前的数为l，
我们发现，如果一个数，前面或后面出现了与它同类的数，那么它被删掉就对答案没有影响，反则+1，
转移的时候枚举一下从上一轮的哪一个数转移过来，分类一下当前取不取数，
转移方程相信读者们是可以推出来的，太长了不想写

复杂度： O(nm∗28∗8)

Code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define NX(x) ((x)&(-(x)))
using namespace std;
const int N=120;
int read(int &n)
{
char ch=' ';int q=0,w=1;
for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
if(ch=='-')w=-1,ch=getchar();
for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int n,m,m1,ans,M;
int a[N];
int zg[11];
int er[11];
bool z[N];
int f[N][N][260][10];
int z1[50];
int main()
{
er[1]=1;fo(i,2,10)er[i]=er[i-1]<<1;
int q,w,_;w=0;
read(n),read(m);
fo(i,1,n)
{
read(q);if(!z1[q])z1[q]=++w;
a[i]=z1[q];
}
M=w;
fod(i,n,1)
{
if(zg[a[i]])z[i]=1;
zg[a[i]]++;
}
memset(f,127,sizeof(f));
f[0][0][0][0]=0;
ans=1e9;
fo(i,1,n)
fo(j,0,m)
fo(k,0,er[M+1]-1)
{
if(k&er[a[i]])
fo(k1,0,M)
{
f[i][j][k][a[i]]=min(f[i][j][k][a[i]],min((k1!=a[i])+f[i-1][j][k][k1],f[i-1][j][k-er[a[i]]][k1]+1));
}
if(j)
fo(k1,0,M)if(k&er[k1]||k1==0)
{
f[i][j][k][k1]=min(f[i][j][k][k1],((k&er[a[i]])==0&&!z[i])+f[i-1][j-1][k][k1]);
}
if(i==n)fo(k1,1,M)ans=min(ans,f[i][j][k][k1]);
}
printf("%dn",ans);
return 0;
}

最后

以上就是幽默期待为你收集整理的【JZOJ 3853】帮助BsnyDescriptionSolutionCode的全部内容，希望文章能够帮你解决【JZOJ 3853】帮助BsnyDescriptionSolutionCode所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。