描述

小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 136 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 0x3f3f3f3fusing 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;}