2813 - 帮助Bubu
时间限制 : 2 秒
内存限制 : 128 MB
Bubu的书架乱成一团了！帮他一下吧！
他的书架上一共有n本书。我们定义混乱值是连续相同高度书本的段数。例如，如果书的高度是30,30,31,31,32,那么混乱值为3，30,32,32,31的混乱度也是3,但31,32,31,32,31的混乱度是5-这实在是太乱了。
Bubu想尽可能的减少混乱度，但他有点累了，所以他决定最多取出k本书，再随意将他们放到书架上。你能帮助他吗？
题目输入
Input:
最多会有20组测试数据。每组测试数据开头为两个整数n,k(1<=k<=n<=100),表示总共有n本书，最多可以进行k次搬书操作。接下来一行有n个整数，表示每本书的高度，从左到右。每本书的高度是25到32间的整数。最后一组数据后有一行n=k=0。
题目输出
Output:
对于每一组数据，输出Case标号和最终最小的混乱度。在每组数据后打印一个空行。
输入/输出样例
输入格式
5 2 25 25 32 32 25 5 1 25 26 25 26 25 0 0
输出格式
Case 1: 2 Case 2: 3
C++解答
#include<cstdio> #include<cstring> using namespace std; #define min(a,b) ((a)<(b)?(a):(b)) #define inf ((1<<30)-1) int dp[2][105][1<<8][10]; int tall[105],num[1<<8]; int main() { int n,m,begin; //预处理 memset(num,0,sizeof(num)); for(int i=0; i<(1<<8); ++i) for(int j=0; j<8; ++j) if(i&(1<<j)) num[i]++; for(int cas=1;~scanf("%d%d",&n,&m);++cas) { if(n+m==0) break; begin=0;//初始高度状态 for(int i=1; i<=n; ++i) { scanf("%d",&tall[i]); tall[i]-=25; begin=begin|(1<<tall[i]); } for(int i=0; i<=m; ++i)//取走的次数 for(int j=0; j<(1<<8); ++j)//高度状态 for(int k=0; k<=8; ++k)//最后的书的高度 dp[0][i][j][k]=inf; dp[0][0][0][8]=0;//起始点 for(int i=1; i<=n; ++i) { for(int j=0; j<=m; ++j) for(int k=0; k<(1<<8); ++k) for(int s=0; s<=8; ++s) dp[i&1][j][k][s]=inf; for(int j=0; j<i&&j<=m; ++j) for(int k=0; k<(1<<8); ++k) for(int s=0; s<=8; ++s) if(dp[(i-1)&1][j][k][s]!=inf) { //取走第i位 if(j<m) dp[i&1][j+1][k][s]=min(dp[i&1][j+1][k][s],dp[(i-1)&1][j][k][s]); //不取走第i位且高度与前一个相同 if(s==tall[i]) dp[i&1][j][k][s]=min(dp[i&1][j][k][s],dp[(i-1)&1][j][k][s]); //不取走第i位且高度与前一个不同 else dp[i&1][j][k|(1<<tall[i])][tall[i]]=min(dp[i&1][j][k|(1<<tall[i])][tall[i]],dp[(i-1)&1][j][k][s]+1); } } int ans=inf; for(int i=0; i<=m; ++i) for(int j=0; j<(1<<8); ++j) for(int k=0; k<8; ++k) if(dp[n&1][i][j][k]!=inf) { int temp=j^begin;//不在此状态且拿出的书的高度 if(ans>dp[n&1][i][j][k]+num[temp]) ans=dp[n&1][i][j][k]+num[temp]; } printf("Case %d: %d\n\n",cas,ans); } return 0; }