農(nóng)夫有一塊地要養(yǎng)牛，有草的地方才能放牛且牛不能相鄰放置，求不同放法的總數(shù)。需要用狀態(tài)壓縮的方法保存每一種放置的狀態(tài)，例如二進(jìn)制101表示第一格和第三個(gè)放置了牛，轉(zhuǎn)換為10進(jìn)制就是5，于是每一個(gè)數(shù)字就對(duì)應(yīng)了一種放置狀態(tài)。1.首先處理出每一排那些狀態(tài)不會(huì)有牛同排相鄰，例如011(2進(jìn)制)=3(10進(jìn)制)就有兩頭牛相鄰，所以(i&(i << 1)) == 0即該狀態(tài)同排不會(huì)有牛相鄰。2.將map有草的地方對(duì)應(yīng)的二進(jìn)制位置設(shè)為0，其余為1，則當(dāng)某種放法全放在草地上，則該狀態(tài)的十進(jìn)制a&map==0。3.對(duì)于相鄰的兩行的狀態(tài)a和b，若a&b==0則這相鄰兩行的這兩種狀態(tài)不存在相鄰的牛，該情況可行。
#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行狀態(tài)為y時(shí)的情況總和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;//所有的狀態(tài)0表示全都不放，最大的表示全放 for (int i = 0; i <= upper; i++){//判斷哪幾種方法不會(huì)有同行相鄰的 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])){//判斷這種狀態(tài)滿足出現(xiàn)在該地圖嗎 for (int k = 0; k <= kk; k++){ if (!(f[k] & f[j])){//兩行與運(yùn)算為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每科作業(yè)每超出期限一天，就扣一分，問如何安排順序，使得總扣分?jǐn)?shù)最小。用狀態(tài)壓縮的方法保存哪些作業(yè)做完了，二進(jìn)制位為1表示作業(yè)完成了，0表示還沒做。從小到大枚舉每種作業(yè)完成狀態(tài)，然后枚舉作業(yè)，遞推得出最優(yōu)解。
#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>using namespace std;const int MAXN = 1 << 16;struct Node{ int cost;//已用時(shí)間 int pre;//前一狀態(tài) int reduced;//最少損失的分?jǐn)?shù) }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++)//遍歷所有狀態(tài) { for (int work = 0; work<n; work++) { int cur = 1 << work; if ((cur&j) == 0)//該項(xiàng)作業(yè)尚未做過 { 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])//該狀態(tài)已有訪問信息 { 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);//遞歸輸出 }}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
