題目描述
每天，巧克力在它的許多形式上被全世界數(shù)百萬人分享。它是一個真正普遍的糖果，實際上在世界上每個國家都能得到。
你發(fā)現(xiàn)唯一比吃巧克力更好的事情是把它分享給朋友。不幸的是，你的朋友非常挑剔，有著不同的胃口：有的喜歡讓你提供較多的巧克力，而其他的喜歡讓你提供較少的巧克力。你發(fā)現(xiàn)當(dāng)他們的要求可以相互疊加時，這個事情就變得越來越難決斷。現(xiàn)在是寫一個程序來一次性完全解決這個問題的時間！
你的巧克力是矩形的。巧克力由同樣大小的矩形塊組成。你可以沿著巧克力中行或者列的分割線將巧克力分成兩塊來分享你的巧克力。你可以重復(fù)地用同樣手段將分成的小塊繼續(xù)分割。你的每個朋友堅持要得到巧克力中的一個矩形部分，這個部分包含一個確定地小塊數(shù)。你也有些堅持心：如果這塊巧克力能全部分給你的朋友，不剩下任何部分，你才會分割你的巧克力。
例如圖9表示將一個由3×4個小塊組成巧克力塊分割3次，分成各自包含6、3、2、1個小塊的4部分的一種方法。（這相當(dāng)于輸入樣例中第一個測試數(shù)據(jù)。）

輸入
輸入數(shù)據(jù)包含多組測試數(shù)據(jù)，每組測試數(shù)據(jù)描述一個要分享的巧克力塊。每組測試數(shù)據(jù)的第一行包含一個整數(shù)n(1<=n<=15)，表示巧克力需要分割成的塊數(shù)。第二行包含兩個整數(shù)x、y，表示巧克力塊的兩個方向上的長度。第三行包含n個正整數(shù)，表示n個部分各自需要包含的小塊數(shù)。
輸入數(shù)據(jù)終止于只包含整數(shù)0的一行。
輸出
對于每組測試數(shù)據(jù)，先輸出它的測試點編號。然后輸出將巧克力按照指定的方法分割是否有可能：如果可能，輸出“Yes”，否則輸出“No”。按照輸出樣例中的格式輸出。
樣例輸入
4
3 4
6 3 2 1
2
2 3
1 5
0
樣例輸出
Case 1: Yes
Case 2: No
第一次做這種難度的狀壓dp。簡單的說一下自己的理解吧，因為有一些東西我也沒有理解透，參考著看一下吧。
思路：
第一眼看到題目，很多人肯定想的是，怎么用給定的這些巧克力將r * c的巧克力表示出來。但是這些巧克力長和寬都不一樣，怎么表示？很難。那么我們就轉(zhuǎn)換一下思路，不去表示r*c的巧克力，而是怎么用r * c的巧克力，一下一下的切，從而得到這些小的巧克力。一整塊大的巧克力，只能橫著切或者豎著切，例如一塊r * c的巧克力，橫著切的話，分別得到（（r-r0） * c）和（r0 * c）的兩塊巧克力。豎著切也是一樣的。
并且，切出來的長方形可以任意組合的，比如要切出兩塊4的和2的巧克力，你不用管它怎么組合，怎么拼在一起的，它肯定是由一塊6的巧克力切出來的。
接下來就說說怎么實現(xiàn)代碼了。
所謂的狀壓，這個題目，n很小，那么我們就從n下手。我們把（0~(1<<n)-1）這些狀態(tài)所代表的巧克力大小都計算出來。例如10101，就代表的是第1,3,5塊巧克力所代表的巧克力和。最終的狀態(tài)是S（11111），它是由x * y的巧克力來形成的。現(xiàn)在我們知道了總面積S，那么我們再知道一條邊，就可以表示出另外一條邊了，這樣的話，就可以縮小一維，降低時間復(fù)雜度。
記憶化搜索代碼如下：

inline int check(int s)//這一部分，類似于求二進制中1的個數(shù)，也就是求巧克力的塊數(shù)。 {if(s==0) return 0;else return check(s>>1)+(s&1); } inline int dfs(int s,int x) {if(dp[s][x]!=-1) return dp[s][x];if(check(s)==1) return dp[s][x]=1;//如果還剩下一塊巧克力，這塊巧克力一定可以拼出這個形狀。int y=sum[s]/x;for(int s0=(s-1)&s;s0;s0=(s0-1)&s)//這里自己模擬一下吧，利用&運算分離出s中的1.{int s1=s-s0;//這里最好自己模擬一下，位運算的神秘之處，很巧妙的就可以表達出所有的狀態(tài)。if(sum[s0]%x==0&&dfs(s0,min(x,sum[s0]/x))&&dfs(s1,min(x,sum[s1]/x))) return dp[s][x]=1;//橫著切，分成上下兩部分，只有這上下兩部分都符合，這個狀態(tài)才符合。if(sum[s0]%y==0&&dfs(s0,min(y,sum[s0]/y))&&dfs(s1,min(y,sum[s1]/y))) return dp[s][x]=1;//豎著切，分成左右兩部分，只有左右兩部分都符合，這個狀態(tài)才符合。}return dp[s][x]=0; }

整體代碼：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1<<17; int dp[maxx][107],sum[maxx],a[maxx]; int n;inline int check(int s) {if(s==0) return 0;else return check(s>>1)+(s&1); } inline int dfs(int s,int x) {if(dp[s][x]!=-1) return dp[s][x];if(check(s)==1) return dp[s][x]=1;int y=sum[s]/x;for(int s0=(s-1)&s;s0;s0=(s0-1)&s){int s1=s-s0;if(sum[s0]%x==0&&dfs(s0,min(x,sum[s0]/x))&&dfs(s1,min(x,sum[s1]/x))) return dp[s][x]=1;if(sum[s0]%y==0&&dfs(s0,min(y,sum[s0]/y))&&dfs(s1,min(y,sum[s1]/y))) return dp[s][x]=1;}return dp[s][x]=0; } int main() {int k=0;while(scanf("%d",&n),n){memset(sum,0,sizeof(sum));memset(dp,-1,sizeof(dp));int x,y;scanf("%d%d",&x,&y);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int s=0;s<(1<<n);s++)//枚舉所有可能的狀態(tài)，然后這個狀態(tài)下，所有位置為1的，就代表有這一塊巧克力，那么就加上這一塊巧克力的大小。for(int i=1;i<=n;i++) if(s&(1<<(i-1))) sum[s]+=a[i];int all=(1<<n)-1;int flag=0;if(sum[all]!=x*y||sum[all]%min(x,y)) flag=0;else flag=dfs(all,min(x,y));printf("Case %d: %s\n",++k,flag==1?"Yes":"No");}return 0; }

很好的一道題目，思維量很大。
努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯][算法提高VIP]Sharing Chocolate（状压dp记忆化搜索）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。