农夫有一块地要养牛，有草的地方才能放牛且牛不能相邻放置，求不同放法的总数。需要用状态压缩的方法保存每一种放置的状态，例如二进制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;}每科作业每超出期限一天，就扣一分，问如何安排顺序，使得总扣分数最小。用状态压缩的方法保存哪些作业做完了，二进制位为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);//递归输出 }}新闻热点
疑难解答
