農夫有一塊地要養牛，有草的地方才能放牛且牛不能相鄰放置，求不同放法的總數。需要用狀態壓縮的方法保存每一種放置的狀態，例如二進制101表示第一格和第三個放置了牛，轉換為10進制就是5，于是每一個數字就對應了一種放置狀態。1.首先處理出每一排那些狀態不會有牛同排相鄰，例如011(2進制)=3(10進制)就有兩頭牛相鄰，所以(i&(i << 1)) == 0即該狀態同排不會有牛相鄰。2.將map有草的地方對應的二進制位置設為0，其余為1，則當某種放法全放在草地上，則該狀態的十進制a&map==0。3.對于相鄰的兩行的狀態a和b，若a&b==0則這相鄰兩行的這兩種狀態不存在相鄰的牛，該情況可行。
#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>using namespace std;const int MAXN = 1 << 13;int map[13], f[MAXN];int dp[13][MAXN];//dp[x][y]第x行狀態為y時的情況總和int n, m;int main(){ int x; scanf("%d%d", &n, &m); memset(map, 0, sizeof(map)); for (int i = 1; i <= n; i++){ for (int j = 0; j < m; j++){ scanf("%d", &x); if (x == 0)//能放的為0，不能放的為1 map[i] += (1 << j); } } int kk = -1; int upper = (1 << m) - 1;//所有的狀態0表示全都不放，最大的表示全放 for (int i = 0; i <= upper; i++){//判斷哪幾種方法不會有同行相鄰的 if ((i&(i << 1)) == 0) f[++kk] = i; } memset(dp, 0, sizeof(dp)); for (int i = 0; i <= kk; i++){//判斷第一行 if (!(f[i] & map[1])) dp[1][f[i]] = 1; } for (int i = 2; i <= n; i++){ for (int j = 0; j <= kk; j++){ if (!(f[j] & map[i])){//判斷這種狀態滿足出現在該地圖嗎 for (int k = 0; k <= kk; k++){ if (!(f[k] & f[j])){//兩行與運算為0說明無相鄰 dp[i][f[j]] += dp[i - 1][f[k]]; } } } } } int ans = 0; for (int i = 0; i <= kk; i++){ ans += dp[n][f[i]]; } Doing Homework HDU - 1074每科作業每超出期限一天，就扣一分，問如何安排順序，使得總扣分數最小。用狀態壓縮的方法保存哪些作業做完了，二進制位為1表示作業完成了，0表示還沒做。從小到大枚舉每種作業完成狀態，然后枚舉作業，遞推得出最優解。
#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>using namespace std;const int MAXN = 1 << 16;struct Node{ int cost;//已用時間 int pre;//前一狀態 int reduced;//最少損失的分數 }dp[MAXN];bool visited[MAXN];struct Course{ int deadtime;//截止日期 int cost;//所需日期 char name[201];}course[16];void output(int status){ int curjob = dp[status].pre^status; int curid = 0; curjob >>= 1; while (curjob) { curid++; curjob >>= 1; } if (dp[status].pre != 0) { output(dp[status].pre); } printf("%s/n", course[curid].name);}int main(){ int T, n, i, j; scanf("%d", &T); while (T--) { scanf("%d", &n); int tupper = (1 << n)-1; for (i = 0; i<n; i++) { scanf("%s%d%d", &course[i].name, &course[i].deadtime, &course[i].cost); } memset(visited, false, sizeof(visited)); dp[0].cost = 0; dp[0].pre = -1; dp[0].reduced = 0; visited[0] = true; for (j = 0; j<tupper; j++)//遍歷所有狀態 { for (int work = 0; work<n; work++) { int cur = 1 << work; if ((cur&j) == 0)//該項作業尚未做過 { int curtemp = cur | j; int day = dp[j].cost + course[work].cost; dp[curtemp].cost = day; int reduce = day - course[work].deadtime; if (reduce<0)reduce = 0; reduce += dp[j].reduced; if (visited[curtemp])//該狀態已有訪問信息 { if (reduce<dp[curtemp].reduced) { dp[curtemp].reduced = reduce; dp[curtemp].pre = j; } } else //沒有訪問過 { visited[curtemp] = true; dp[curtemp].reduced = reduce; dp[curtemp].pre = j; } } } } printf("%d/n", dp[tupper].reduced); output(tupper);//遞歸輸出 }}新聞熱點
疑難解答
