hihocoder #1044 状态压缩dp

2/22/2017来源:ASP.NET技巧人气:1785

描述

小Hi和小Ho在兑换到了喜欢的奖品之后,便继续起了他们的美国之行,思来想去,他们决定乘坐火车前往下一座城市——那座城市即将举行美食节!

但是不幸的是,小Hi和小Ho并没有能够买到很好的火车票——他们只能够乘坐最为破旧的火车进行他们的旅程。

不仅如此,因为美食节的吸引,许多人纷纷踏上了和小Hi小Ho一样的旅程,于是有相当多的人遭遇到了和小Hi小Ho一样的情况——这导致这辆车上的人非常非常的多,以至于都没有足够的位置能让每一个人都有地方坐下来。

小Hi和小Ho本着礼让他们的心情——当然还因为本来他们买的就是站票,老老实实的呆在两节车厢的结合处。他们本以为就能够这样安稳抵达目的地,但事与愿违,他们这节车厢的乘务员是一个强迫症,每隔一小会总是要清扫一次卫生,而时值深夜,大家都早已入睡,这种行为总是会惊醒一些人。而一旦相邻的一些乘客被惊醒了大多数的话,就会同乘务员吵起来,弄得大家都睡不好。

将这一切看在眼里的小Hi与小Ho决定利用他们的算法知识,来帮助这个有着强迫症的乘务员——在不与乘客吵起来的前提下尽可能多的清扫垃圾。

小Hi和小Ho所处的车厢可以被抽象成连成一列的N个位置,按顺序分别编号为1..N,每个位置上都有且仅有一名乘客在休息。同时每个位置上都有一些垃圾需要被清理,其中第i个位置的垃圾数量为Wi。乘务员可以选择其中一些位置进行清理,但是值得注意的是,一旦有编号连续的M个位置中有超过Q个的位置都在这一次清理中被选中的话(即这M个位置上的乘客有至少Q+1个被惊醒了),就会发生令人不愉快的口角。而小Hi和小Ho的任务是,计算选择哪些位置进行清理,在不发生口角的情况下,清扫尽可能多的垃圾。

提示一:无论是什么动态规划,都需要一个状态转移方程!

提示二:好像什么不对劲?状态压缩哪里去了?

输入

每个测试点(输入文件)有且仅有一组测试数据。

每组测试数据的第一行为三个正整数N、M和Q,意义如前文所述。

每组测试数据的第二行为N个整数,分别为W1到WN,代表每一个位置上的垃圾数目。

对于100%的数据,满足N<=1000, 2<=M<=10,1<=Q<=M, Wi<=100

输出

对于每组测试数据,输出一个整数Ans,表示在不发生口角的情况下,乘务员最多可以清扫的垃圾数目。

样例输入
5 2 1
36 9 80 69 85 

样例输出

201

思路:由于m比较小我们可以采用状态压缩 还是开二维数组 dp[i][j] 前i个位置j状态下清扫垃圾的最大量;如果当前j的末位置状态位1我们就代表当前i是选择的,否则就是不选择.而且在实现过程中j始终表示的是m为的二进制,我们用j表示的二进制中1的个数来表示是否超过Q(并且要时刻注意是一段连续的m序列中不能超过q)如果超过Q第i个位置只能不选,否则可以考虑选与不选的最大值.

问题的分析:

(1)这不是背包!相同点:都是n个东西,每次多考虑一个。不同点:背包有容量限制可以作为列数进行dp,而这里没有(也就不能开一个二维数组了),却给出了位置的数量方面的限制。

(2)既然要用动态规划,那就要从小问题开始考虑,而较大问题要依靠较小的问题来进行决策计算。小问题:最小就是只有1个位置了。每次考虑的增加规模量:每次多考虑1个位置,直到n个全考虑了。

(3)假如m=n,那简单了,问题转成:在n个位置上选出q个,使得垃圾的总数量最多。穷举:2^n种可能,这里边还要去掉一些位置个数大于q的(大于q就是非法),剩下来的才是所有的可能(只是垃圾量的问题,都是合法的)。

(4)假如n>m,那麻烦了。我们先在前m个进行决策(也就是第3所分析的一样),那么第m+1个应该考虑2~m这里面有没有达到q,达到了,那就只能不清理了;若没有达到,那还可以选择清or不清。为什么会有选择不清的情况?有得清还不赶紧清了吗?原因是,如果你这一步选择清理了,那第m+2个位置就要考虑从3到m+1的位置上有没有达到q,达到了,这一步又肯定没得选择了。假设只有m+2个,前面1~m个位置上已经决策完成,而第m+1个位置上的垃圾极少,第m+2个位置上的垃圾超多,由于在前3~m个位置上的决策只是选了q-1个,但是你在第m+1个位置上选择了清理,那么第m+2个位置上的超多垃圾清不到了。

(5)结论是:每一次决定第i个位置清or不清理,靠的是前面m-1个位置上的清理数量,跟超过m-1个的都没有任何关系。前面穷举的结果在符合规则的条件下不影响后面的决策,你仍可选择不清理。

 

关于实现:

(1)肯定是个二维数组来保存状态,数组中保存什么?肯定是第i行(包括)之前所做出的决定所清理的垃圾总量。那列是什么?是第i行(包括)之前m个位置上是否清理的信息。考虑到m<=10,那么十位的二进制最多能表达1023,这就是数组列的上限。那么dp[i][j]表示:前 i 个位置在 j (1的个数信息)这种决策情况下所能获得的最大垃圾量。

(2)看个例子:n有{1, 2, 3, 4, 5, 6, 7, 8, 9}共9个位置,m限制为5,上限q为3。

  {1, 2, 3, 4, 5, 6, 7, 8, 9}  //假设1~5已经考虑完了。准备考虑第6个

  {1, 2, 3, 4, 5, 6, 7, 8, 9}  //考虑6不需要关心1了。而d[6][j]记录的是1~6的的所决定清理的垃圾量,而j只用5个位来表示2~6的存放情况。假设j={10101}b二进制.也就是第2,4,6位置上决定了清理,那么dp[6][j]=" w[] " + w[2]+w[4]+w[6]。这红色的w[]代表第1个的决策结果,具体清没清理,得从dp[5][j>>1]和dp[5][(j>>1)+(1<<4)]看谁大来决定了,小的那个没有必要保存了,1~5的垃圾量明显会比别人小,先淘汰了。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e3+10;
int dp[maxn][1030];
int w[maxn];
int n,m,q;
int check(int m)//求二进制中的1个数
{
	int ans=0;
	while(m)
	{
		if(m&1)
			ans++;
		m>>=1;
		
	}
	return ans;
}
int main()
{
	int i,j;
	scanf("%d%d%d",&n,&m,&q);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&w[i]);
	}
	memset(dp,0,sizeof(dp));
	for(i=1;i<=n;i++)
	{
		for(j=0;j<1<<m;j++)
		{
			if(check(j)>q)
			continue;
			if(j&1)
				dp[i][j]=max(dp[i-1][j>>1],dp[i-1][(j>>1)+(1<<m-1)])+w[i];//第i个位置选择时的最大值取决于前面i-1个位置 最高位选与不选的最大值.剩下四位的状态不能够改变
			else
				dp[i][j]=max(dp[i-1][j>>1],dp[i-1][(j>>1)+(1<<m-1)]); 
		}
	}
	int ans=-1;
	for(j=0;j<1<<m;j++)
	{
		ans=max(ans,dp[n][j]);
	}
	PRintf("%d\n",ans);
	return 0;
}