題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4336 題意： 　　有n種卡片(n <= 20)。 　　對于每一包方便面，里面有卡片i的概率為p[i]，可以沒有卡片。 　　問你集齊n種卡片所買方便面數量的期望。 ? 題解： 　　狀態壓縮

引入?首先來說說“狀態壓縮動態規劃”這個名稱，顧名思義，狀態壓縮動態規劃這個算法包括兩個特點，第一是“狀態壓縮”，第二是“動態規劃”。?狀態壓縮：?從狀態壓縮的特點來看，這個算法適用的題目符合以下的條件：?1.解法需要保

? http://poj.org/problem?id=1185 poj2352，題意： ? 狀壓dp入門，思路： 每一行最多只有10列，所以可以用二進制來表示每一行的狀態。 d【i】【j】【k】表示第i行狀態為k時，并且上一行狀態為j時的最大炮兵數。 1 #include<iostream> 2 #

題目傳送門:580D ? 題目大意:給你n道菜以及每道菜一個權值,k個條件,即第y道菜在第x道后馬上吃有z的附加值,求從中取m道菜的最大權值 看到這道題,我們會想到去枚舉,但是很顯然這是會超時的,再一看數據范圍,n只有18,那么我們就可以用狀壓去做了,dp數組也還是比較好定義的,dp[i]

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4284 思路：類似于poj3311:http://poj.org/problem?id=3311,首先floyd預處理出兩點之間的最短距離，然后就是枚舉所有的狀態了。 1 #include<iostream> 2 #include<cstdio> 3 #in

Corn Fields Description Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are in