算法练习系列—hiho1044 状态压缩二(捡垃圾)

我会带着你远行 2022-08-07 03:59 116阅读 0赞

**题目地址**：[http://hihocoder.com/problemset/problem/1044][http_hihocoder.com_problemset_problem_1044]

**算法思路：**此题可以看做是铺地砖的变形，没有明显的行数和状态，但是我们可以自己将其中的行和状态给扣出来。其中第一行就是N个数的中前(0,1,2…M-1), 第二行就是(2,3..M)…一直到最后一行为(N-M…N)。每一行的状态个数即为2^M-1(即这M个位置要么填写1，要么填写0)。此时可用F\[i\]\[j\]表示第i行状态为j时的垃圾最大值。最终的结果就是第N-M行所对应的状态中的最大值。

上一遍blog对状态压缩讲的比较详细，可以参看 [http://blog.csdn.net/lu597203933/article/details/44137277][http_blog.csdn.net_lu597203933_article_details_44137277]

**代码：**

#include <iostream>
    #include <memory.h>
    #include <time.h>
    using namespace std;
    #define NMax 1000
    #define MMax 1 << 10
    long long F[NMax][MMax];
    
    bool testCompatibility(int j, int M, int Q)     // 判断该状态j是否是连续的M中有大于Q个1
    {
    	int i = 0;
    	int count = 0;
    	while(i < M)
    	{
    		if(j & (1 << i))
    		{
    			count ++;
    		}
    		i++;
    	}
    	if(count > Q)return false;
    	else return true;
    }
    long long getFirstLine(int j, int M, int *W)   //  得到“第一行”的垃圾总量
    {
    	int i = 0;
    	long long rubbish = 0;
    	while(i < M)
    	{
    		if(j & (1 << i))
    		{
    			rubbish += W[M-1-i];
    		}
    		i++;
    	}
    	return rubbish;
    }
    
    bool testRemaining(int j, int k, int M)     // 判断j的最高M-1位是否等于k的低M-1位  即判断状态j与上一状态k是否兼容
    {
    	k = k & ~(1<<(M-1));   // 将k的第M-1位置0
    	k = k << 1;
    	k = k | (j & 1);
    	if (k == j) return true;
    	else return false;
    }
    
    
    int main()
    {
    	int N, M, Q;
    	while(cin >> N >> M >> Q){
    		int W[NMax];
    		int sta[NMax];
    		int tt = 0;
    		int allStates = 1 << M;
    		int i, j;
    		for(i = 0; i < N; i++)
    			cin >> W[i];
    	
    		memset(F, 0 , sizeof(F));
    		long long maxRubbish = 0;
    
    		for(j = 0; j < allStates; j++)
    		{
    			if(testCompatibility(j, M, Q))
    			{
    				sta[tt++] = j;		  //  将可用的状态保存到一个数组sta中  如果没有这个sta 则需要遍历所有的状态
    			}
    		}
    
    		for(int j = 0; j < tt; j++)
    			F[0][j] = getFirstLine(sta[j], M, W);   // 得到前m个单元的状态
    
    		for(i = 1; i <= N - M; i++)
    		{
    			for(j = 0; j < tt; j++)
    			{
    				for(int k = 0; k < tt; k++)
    				{
    					int aa = sta[k] & ~(1<<(M-1));   // 将k的第M-1位置0
    					aa = aa<< 1;
    					aa = aa | (sta[j] & 1);
    					//if(testRemaining(sta[j], sta[k], M))       //  在循环中尽量不要用函数，否则调用开销会很大
    					if(aa == sta[j])
    					{
    						F[i][j] = max(F[i-1][k],F[i][j]);
    					}
    				}
    				if(((sta[j] & 1) == 1))
    				{
    					F[i][j] += W[i+M-1];
    				}
    			}
    		}
    
    		for(int j = 0; j < tt; j++)
    			maxRubbish = max(maxRubbish, F[N-M][j]);
    		cout << maxRubbish << endl;
    	}
    	return 0;
    }
    
    /*
    input:
    5 2 1
    36 9 80 69 85
    
    10 8 3
    38 98 97 87 76 67 56 65 53 76
    
    output:
    201
    362
    */

但是此题我代码提交的时候TLE，显示超时了，但是我自己将所用时间输出来了了，比网上给的代码[http://hhfgeg.name/?id=158][http_hhfgeg.name_id_158]还有少，但始终TLE，不知道为什么，有知道的可以评论。谢谢！

**下面总结一般状态压缩的解法步骤**

1：将题目转换成状态压缩的问题，F\[i\]\[j\]表示第i行状态为j时的最大方案数。

2：初始化，初始化第0行各状态所对应的方案数(垃圾量)

3：通过判断第i行的状态j是否与上一行的各状态的兼容性去求F\[i\]\[j\]

4:通过题目求出最终的结果

[http_hihocoder.com_problemset_problem_1044]: http://hihocoder.com/problemset/problem/1044
[http_blog.csdn.net_lu597203933_article_details_44137277]: http://blog.csdn.net/lu597203933/article/details/44137277
[http_hhfgeg.name_id_158]: http://hhfgeg.name/?id=158