描述

小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

題解：wa了幾發，發現是沒有認真分析轉移：

1.如果不掃?dp[p][j>>1]=max(dp[p][j>>1],dp[p^1][j]);

2.如果掃?dp[p][add(j)]=max(dp[p][add(j)],dp[p^1][j]+x);

做的時候天真地認為只有一個max，呵呵噠。。。

而且更好玩的是。。。一開始我的狀壓跟正常人是反著的，寫起來hentai的不行。。。。

1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 #include<cstring> 7 #define PAU putchar(' ') 8 #define ENT putchar('\n') 9 using namespace std; 10 int n,m,q,lim; 11 const int maxd=(1<<10)+10; 12 int ones[maxd],dp[2][maxd]; 13 int digcnt(int S){ 14 int ans=0;while(S)S=S^(S&-S),ans++;return ans; 15 } 16 void calones(){ 17 for(int i=0;i<lim;i++)ones[i]=digcnt(i);return; 18 } 19 int add(int S){return (1<<(m-1))|(S>>1);} 20 inline int read(){ 21 int x=0,sig=1;char ch=getchar(); 22 for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=0; 23 for(;isdigit(ch);ch=getchar())x=10*x+ch-'0'; 24 return sig?x:-x; 25 } 26 inline void write(int x){ 27 if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x; 28 int len=0,buf[15];while(x)buf[len++]=x%10,x/=10; 29 for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return; 30 } 31 void init(){ 32 n=read();m=read();q=read();lim=1<<m;calones(); 33 int x,p=0; 34 for(int i=0;i<n;i++){ 35 x=read();p^=1; 36 for(int j=0;j<lim;j++)if(ones[j]<=q){ 37 dp[p][j>>1]=max(dp[p][j>>1],dp[p^1][j]); 38 if(ones[j>>1]<q)dp[p][add(j)]=max(dp[p][add(j)],dp[p^1][j]+x); 39 } 40 }int ans=0;for(int S=0;S<lim;S++)ans=max(ans,dp[p][S]);write(ans); 41 return; 42 } 43 void work(){ 44 return; 45 } 46 void print(){ 47 return; 48 } 49 int main(){init();work();print();return 0;}

tips：要讓位移操作價值更大！

? ? ? ? 轉移的時候把轉移最好寫成目標狀態=已知狀態，寫起來舒服一點。

轉載于:https://www.cnblogs.com/chxer/p/4716483.html

總結

以上是生活随笔為你收集整理的hiho #1044 : 状态压缩·一的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。