首页 > ACM题库 > HDU-杭电 > HDU 3237-Help Bubu-动态规划-[解题报告]HOJ
2014
03-09

HDU 3237-Help Bubu-动态规划-[解题报告]HOJ

Help Bubu

问题描述 :

Bubu’s bookshelf is in a mess! Help him!

There are n books on his bookshelf. We define the mess value to be the number of segments of consecutive equal-height books. For example, if the book heights are 30, 30, 31, 31, 32, the mess value is 3, that of 30, 32, 32, 31 is also 3, but the mess value of 31, 32, 31, 32, 31 is 5 – it’s indeed in a mess!

Bubu wants to reduce the mess value as much as possible, but he’s a little bit tired, so he decided to take out at most k books, then put them back somewhere in the shelf. Could you help him?

输入:

There will be at most 20 test cases. Each case begins with two positive integers n and k (1 <= k <= n <= 100), the total number of books, and the maximum number of books to take out. The next line contains n integers, the heights of each book, from left to right. Each height is an integer between 25 and 32, inclusive. The last test case is followed by n = k = 0, which should not be processed.

输出:

There will be at most 20 test cases. Each case begins with two positive integers n and k (1 <= k <= n <= 100), the total number of books, and the maximum number of books to take out. The next line contains n integers, the heights of each book, from left to right. Each height is an integer between 25 and 32, inclusive. The last test case is followed by n = k = 0, which should not be processed.

样例输入:

5 2
25 25 32 32 25
5 1
25 26 25 26 25
0 0

样例输出:

Case 1: 2

Case 2: 3

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3237

题目大意一个书架有n本书,每本书的高度介于25和32之间,n本书中高度连续相同的算一段,一般来说n本书会有很多段,现在可以取出k本书再插进原书架中,问这些书最少有几段?n
<= 100




解题思路:由于书的高度介于25和32之间,可以把书的高度减去25变成介于0和7之间,这个数字就很适合状态压缩了。思考的时候就尽量往高度进行压缩。每本书有两种选择,一种留下,一种抽走,留下的书和抽走的书可以用两个状态表示,如果抽出去的书不在留下的书里面,那么最后就要增加一段。每本书似乎只和留下来的最后一本书的状态有关,如果书的高度和留下的最后一本书的高度相同,那么可以直接合并进去而不必计算高度,如果不相同则要增加段数。

    那我们要怎么表示抽走的状态呢?压缩成一个数字吗?不行,还必须和k扯上关系,也就是说必须有一维表示数量,而抽走书的种类可以用总状态减去留下来的状态来表示。这样就可以用dp[i][j][k][s]来进行状态转移,dp[i][j][k][s]表示到第i本书时取走j本书留下来的书状态为k最后一本书高度为s。状态转移见代码。复杂度O(n*k*(1<<8)*8)。

测试数据:

5 2
25 25 32 32 25
5 1
25 26 25 26 25
0 0

代码

#include <stdio.h>
#include <string.h>
#define MIN 110
#define INF 1047483647
#define min(a,b) (a)<(b)?(a):(b)


int n,m,ht[MIN],ans,one[1<<8]; //one[i]表示状态i中1的个数
int state,dp[2][MIN][1<<8][10];//dp[i][j][k][s]表示到第i行取走j本书剩下的状态数为k最后一本书高度是s时最少连续段数


void Initial() {

    for (int i = 0; i < (1<<8); ++i) {

        for (int j = 0; j < 8; ++j)
            if (i & (1<<j)) one[i]++;
    }
}


int main()
{
    int i,j,k,s,cas = 0;
    int pre,cur,mx,tot;
    Initial();


    while (scanf("%d%d",&n,&m) ,n+m) {

        mx = state = 0;
        for (i = 1; i <= n; ++i) {

            scanf("%d",&ht[i]);
            ht[i] -= 25;
            if (ht[i] > mx) mx = ht[i];       //统计最大的高度
            state |= (1<<ht[i]);
        }

        //Initial
        mx++ ,tot = (1<<mx);
        for (j = 0; j <= m; ++j)
            for (k = 0; k < tot; ++k)
                for (s = 0; s <= mx; ++s)
                    dp[1][j][k][s] = INF;


       dp[1][0][1<<ht[1]][ht[1]] = 1;   //如果第一本书留下来段数就为1
       dp[1][1][0][mx] = 0;             //mx其实是不存在的高度,因为第一本书被拿走了那么留下的最后一本书高度实际是不存在的,用这个只是好转移
       for (i = 2; i <= n; ++i) {

           cur = i & 1;                 //当前状态
           pre = 1 - cur;               //前一个状态


           for (j = 0; j <= m ; ++j)
                for (k = 0; k < tot; ++k)
                    for (s = 0; s <= mx; ++s)
                        dp[cur][j][k][s] = INF;


           for (j = 0; j <= m && j < i; ++j)
               for (k = 0; k < tot; ++k)
                   for (s = 0; s <= mx; ++s) {

                       if (dp[pre][j][k][s] == INF) continue;           //小剪枝,但不剪就TLE
                       int stk = k | (1<<ht[i]);                        //当前的状态
                        if (j < m)                                      //如果还可以取走
                            dp[cur][j + 1][k][s] = min(dp[cur][j + 1][k][s], dp[pre][j][k][s]);
                        if (s == ht[i])                                 //如果和留下来的最后一本高度相同,则当前的书留下来并不增加段数
                            dp[cur][j][k][s] = min(dp[cur][j][k][s],dp[pre][j][k][s]);
                        else                                            //增加一段
                            dp[cur][j][stk][ht[i]] = min(dp[cur][j][stk][ht[i]],dp[pre][j][k][s]+1);
                    }
        }


        cur = n & 1,ans = n;
        for (j = 0; j <= m; ++j)
            for (k = 0; k < tot; ++k)
                for (s = 0; s < mx; ++s) 
                    if (dp[cur][j][k][s] != INF) {

                    int st = state ^ k;
                    ans = min(ans,one[st]+dp[cur][j][k][s]);
                }


        printf("Case %d: %d\n\n",++cas,ans);
    }
}

本文ZeroClock原创,但可以转载,因为我们是兄弟。

参考:http://blog.csdn.net/woshi250hua/article/details/7743328