题目来源：
http://acm.hdu.edu.cn/showproblem.php?pid=3237 用f[i,j,k,s]表示从前i本书中取出j本，没被取出书的状态为k(k不仅要表示书存在的种类，还要具体表示哪类书存在)，没被取出书的最后一本高度为s时，剩下书的最小mess值。由于书按高度分类共有8类，可以用八位二进制来表示剩余书的状态，如果对应位为1则表明该类书存在。各类书存在与否，状态众多，这里可以进行状态压缩。 不考虑被拿出来的书的原因是，我们可以把这些书放到最恰当的位置，对前面求最优值不会产生影响。现在由前i-1本书推后面：对于第i本书，若要取f[i,j+1,k,s]=min{f[i,j+1,k,s],f[i-1,j,k,s]}；若不取分两种情况：第i本书的高度与前面相同时，f[i,j,k,s]=min{f[i,j,k,s],f[i-1,j,k,s]};第i本书的高度与前面不同时，f[i,j,k|(1<<h[i]),h[i]]=min{f[i,j,k|(1<<h[i]),h[i]], f[i,j,k,s]+1}. 最后的答案为：min{f[n,j,k,s]+num(k)},num(k)={k^(书最初的状态)}这个二进制数中1的个数，表示被拿出来的书的种类数。见代码：
#include<iostream>
#define min(a,b) (a<b?a:b)
using namespace std;
const int inf=10000000;
int n,m,begin;
int h[105],num[1<<8];
int f[2][105][1<<8][9];
void Init()
{
int i,j;
memset(num,0,sizeof(num));
for(i=0;i<(1<<8);i++)
{
for(j=0;j<8;j++)
if(i&(1<<j)) num[i]++;
}
}
int main()
{
int test=1;
Init();
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
int i,j,k,s;
begin=0;
for(i=1;i<=n;i++)
{
scanf("%d",&h[i]);
h[i]-=25;
begin=begin|(1<<h[i]);
}
for(i=0;i<=m;i++)
for(j=0;j<(1<<8);j++)
for(k=0;k<=8;k++)
f[0][i][j][k]=inf;
f[0][0][0][8]=0;
for(i=1;i<=n;i++)
{
for(j=0;j<=m;j++)
for(k=0;k<(1<<8);k++)
for(s=0;s<=8;s++)
f[i&1][j][k][s]=inf;
for(j=0;j<=i-1&&j<=m;j++)
for(k=0;k<(1<<8);k++)
for(s=0;s<=8;s++)
if(f[(i-1)&1][j][k][s]!=inf)
{
if(j<m)f[i&1][j+1][k][s]=min(f[i&1][j+1][k][s],f[(i-1)&1][j][k][s]);
if(h[i]==s) f[i&1][j][k][s]=min(f[i&1][j][k][s],f[(i-1)&1][j][k][s]);
else f[i&1][j][k|(1<<h[i])][h[i]]=min(f[i&1][j][k|(1<<h[i])][h[i]],f[(i-1)&1][j][k][s]+1);
}
}
int ans=inf;
for(i=0;i<=m;i++)
for(j=0;j<(1<<8);j++)
for(k=0;k<8;k++)
if(f[n&1][i][j][k]!=inf)
{
int temp=j^begin;
if(ans>f[n&1][i][j][k]+num[temp])
ans=f[n&1][i][j][k]+num[temp];
}
printf("Case %d: %d\n\n",test++,ans);
}
//system("pause");
return 0;
}
posted on 2010-08-23 10:56
wuxu 阅读(417)
评论(0) 编辑 收藏 引用 所属分类:
动态规划