两道状态压缩DP-- POJ 3254,HDU 1074

2/10/2017来源:ASP.NET技巧人气:446

Corn Fields POJ - 3254

农夫有一块地要养牛,有草的地方才能放牛且牛不能相邻放置,求不同放法的总数。需要用状态压缩的方法保存每一种放置的状态,例如二进制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]]; } PRintf("%d\n", (ans % 100000000)); return 0; }

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);//递归输出 } }