UVALive 4490 Help Bubu

　　题目大意：有n本书，高度值域为8，现可以把k本书拿出来再放进去，相邻的、高度相同的书算作一块，最小化块的个数。n=100。

　　强烈建议大家不要在做完区间DP后做别的DP题：区间DP是整体考虑，而一般DP是考虑以i为末尾，思路完全不同。

　　难点好像就在于设状态，状态设出来就可以大力转移了。

　　首先f[i][j]，表示到第几本书、用了几次是肯定要设的，但是这样做会缺少很多信息。在转移的时候，我们需要知道最后一位是什么？所以开到f[i][j][k]。

　　这个就可以DP了。但是答案怎么统计呢？如果最终答案是把几种高度全部扣出来，答案就要比DP值大，但这是我们状态中不能体现的。

　　看到值域这么小，直接设f[i][j][k][l]，表示到第i本书、用了j次取书机会、在书架上的书的集合是k，最后一本书是l的最小块数。

　　初始化：

f[i+1][i][bin[h[i+1]]][h[i+1]]=1;

初始化

　　转移方程就是讨论一下就可以出来的东西了。

　　1.当前书取出来：

f[i+1][j+1][k][l]=min(f[i+1][j+1][k][l],f[i][j][k][l]);

转移1

　　2.当前书不取，这时要与最后一位做比较：

f[i+1][j][k|bin[h[i+1]]][h[i+1]]=min(f[i+1][j][k|bin[h[i+1]]][h[i+1]],f[i][j][k][l]+(h[i+1]!=l));

转移2

　　其中bin表示2的多少次方。

　　在统计答案的时候，要这么统计：

for(int i=0;i<=k;++i)
    for(int j=0;j<bin[8];++j)
      for(int k=0;k<8;++k)
        if(f[n][i][j][k]!=f[0][0][0][0])
          Ans=min(Ans,f[n][i][j][k]+num[U^j]);

统计答案

　　其中num表示二进制下有多少个1。

　　完整代码：

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
#define FILE "4490"
using namespace std;

const int N = 110;
int n,k,bin[10],h[N],f[N][N][1<<8][9],t,Ans,num[1<<8];

inline int gi(){
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline void Min(int &x,int y){
  if(x>y)x=y;
}

inline void solve(int U=0){
  for(int i=1;i<=n;++i)U|=bin[h[i]=gi()-25];
  memset(f,127/3,sizeof(f));Ans=f[0][0][0][0];
  f[1][0][bin[h[1]]][h[1]]=1;
  for(int i=1;i<n;++i){
    f[i+1][i][bin[h[i+1]]][h[i+1]]=1;
    for(int j=0;j<=i && j<=k;++j)
      for(int k=0;k<bin[8];++k)
        for(int l=0;l<8;++l)
          if(f[i][j][k][l]!=Ans){
            Min(f[i+1][j+1][k][l],f[i][j][k][l]);
            Min(f[i+1][j][k|bin[h[i+1]]][h[i+1]],f[i][j][k][l]+(h[i+1]!=l));
          }
  }
  for(int i=0;i<=k;++i)
    for(int j=0;j<bin[8];++j)
      for(int k=0;k<8;++k)
        if(f[n][i][j][k]!=f[0][0][0][0])
          Min(Ans,f[n][i][j][k]+num[U^j]);
  printf("Case %d: %d

",++t,Ans);
}

int main()
{
  freopen(FILE".in","r",stdin);
  freopen(FILE".out","w",stdout);
  bin[0]=1;for(int i=1;i<10;++i)bin[i]=bin[i-1]*2;
  for(int i=1;i<bin[8];++i)num[i]=num[i/2]+(i&1);
  while((n=gi()) && (k=gi()))solve();
  fclose(stdin);fclose(stdout);
  return 0;
}

Help Bubu