状态压缩DP-棋盘模型总结-白红宇

状态压缩DP-棋盘模型总结

阅读量：4312 次

发布时间：2019-06-06

本文共 6939 字，大约阅读时间需要 23 分钟。

论文：《周伟ftfish --- 动态规划之状态压缩》关键之处在于： ①针对棋盘不同限制用dfs把每行可行的状态压缩表示成一个数存到s[]。 ②枚举当前处理行和上一行的状态时根据题目限制判断状态是否互斥。 ③有时棋盘上会有些点不能放置，我们也把一行中不能放置的点压缩成一个数存到no[]中，比如用00011000表示第3列和第4列不能放置。然后处理当前行时如果s[j1] & no[i] == 0表示当前放置情况与不能放置的点不冲突。

sgu 223 Little Kings 棋盘限制：在n*n(n<=10)的棋盘上放k个国王（可攻击相邻的8个格子，不能放其他国王），求方案数。

分析：当前行的状态矛盾只涉及到上一行，并且还有放几个国王的限制，所以设dp[i][j][k]表示处理到第i行，第i行状态为j放了k个国王的方案数 dp[i][j][k] = dp[i-1][j'][k-c[j']].

//sgu 223 状态压缩DP 棋盘#include #include #include #include #include #include #include #include #include #include #include #include #define MID(x,y) ((x+y)>>1)#define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long LL;const int sup = 0x7fffffff;const int inf = -0x7fffffff;int n, k;const int NUM_OF_PLACEMENGT = 520;int s[NUM_OF_PLACEMENGT], c[NUM_OF_PLACEMENGT], place_num;         //the placement of each linelong long dp[13][NUM_OF_PLACEMENGT][103];void dfs(int p, int condition_num, int condition_one_amount){             //Store the placement of each line    if (p == n){        s[++ place_num] = condition_num;        //cout << place_num << " " << s[place_num] << endl;        c[place_num] = condition_one_amount;        return ;    }    dfs(p+1, condition_num << 1, condition_one_amount);    if (!(condition_num & 1))        dfs(p+1, condition_num << 1 | 1, condition_one_amount + 1);    return ;}bool ifok(int s1, int s2){      //decide whether tha current condition and the last condition are comtradictry.    if(s1 & s2) return false;         //和正上方判断    if(s1 & (s2<<1))return false;     //和右上方判断    if(s1 & (s2>>1))return false;     //和左上方判断    return true;}int main(){    while(scanf("%d %d", &n, &k) != EOF){        //cout << n << " " << k << endl;        mem(dp, 0);        place_num = 0;        dp[0][1][0] = 1;        dfs(0, 0, 0);        for (int i = 1; i <= n; i ++){            for (int j1 = 1; j1 <= place_num; j1 ++){                for (int j2 = 1; j2 <= place_num; j2 ++){                    for (int w = 0; w <= k; w ++){                        if (ifok(s[j1], s[j2]) && w-c[j1] >= 0)                            dp[i][j1][w] += dp[i-1][j2][w-c[j1]];                    }                }            }        }        long long res = 0;        for (int j = 1; j <= place_num; j ++)            res += dp[n][j][k];        printf("%I64d\n", res);    }	return 0;}

hdu 4539 郑厂长系列故事——排兵布阵棋盘限制：在n*m(n<=100, m<=10)的棋盘上放士兵，每个士兵的曼哈顿距离2的地方都不能放别的士兵。并且有些地方不能放士兵。求最多能放几个士兵。

分析：因为距离为2可能涉及到上2行的状态，所以设dp[i][j1][j2]表示处理到第i行，第i行状态为j1，第i-1行状态为j2最多能放几个士兵。然后因为某些地方不能放置，需要用到③的s[j1] & no[i]。dp[i][j1][j2] = max(dp[i][j1][j2], dp[i-1][j2][j3])

//HDU 4539 状态压缩DP 棋盘#include #include #include #include #include #include #include #include #include #include #include #include #define MID(x,y) ((x+y)>>1)#define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long LL;const int sup = 0x7fffffff;const int inf = -0x7fffffff;int n, m;const int NUM_OF_PLACEMENGT = 500;int s[NUM_OF_PLACEMENGT], c[NUM_OF_PLACEMENGT], place_num;         //the placement of each lineint dp[2][NUM_OF_PLACEMENGT][NUM_OF_PLACEMENGT];vector  dd[NUM_OF_PLACEMENGT];int no[105];void dfs(int p, int condition_num, int condition_one_amount){             //Store the placement of each line    if (p == m){        s[++ place_num] = condition_num;        //cout << condition_num << endl;        c[place_num] = condition_one_amount;        return ;    }    dfs(p+1, condition_num << 1, condition_one_amount);    if (!(condition_num & 2))        dfs(p+1, condition_num << 1 | 1, condition_one_amount + 1);    return ;}bool ifok(int s1, int s2){      //decide whether tha current condition and the last condition are comtradictry.    //if(s1 & s3)     return false;         //和正上方判断    if(s1 & (s2<<1))    return false;     //和右上方判断    if(s1 & (s2>>1))    return false;     //和左上方判断    return true;}int main(){    while(scanf("%d %d", &n, &m) == 2){        mem(no, 0);        place_num = 0;        mem(dp, -1);        dp[0][1][1] = 0;        dfs(0, 0, 0);        for (int i = 1; i <= n; i ++)        for (int j = 1; j <= m; j ++){            int tmp;            scanf("%d", &tmp);            if (tmp == 0)   no[i] += (1 << (m-j));        }        for (int i = 1; i <= n; i ++)            for (int j1 = 1; j1 <= place_num; j1 ++){                if(s[j1] & no[i])   continue;                for (int j3 = 1; j3 <= place_num; j3 ++){                    if (s[j1] & s[j3])  continue;                    for (int j2 = 1; j2 <= place_num; j2 ++){                        if (ifok(s[j1],s[j2]) && dp[(i-1)&1][j2][j3] != -1){                            dp[i&1][j1][j2] = max(dp[i&1][j1][j2], dp[(i-1)&1][j2][j3] + c[j1]);;                        }                    }                }            }        int res = 0;        for (int j1 = 1; j1 <= place_num; j1 ++)            for (int j2 = 1; j2 <= place_num; j2 ++)                res = max(res, dp[n&1][j1][j2]);        printf("%d\n", res);    }    return 0;}

poj 1185 炮兵阵地棋盘限制：在n*m(n<=100, m<=10)的棋盘上放士兵，每个士兵上下左右2格子内都不能放别的士兵。并且有些地方不能放士兵。求最多能放几个士兵。

分析：和上一题基本一样，就是判断状态互斥时有区别。

//POJ 1185 炮兵阵地 状态压缩DP#include #include #include #include #include #include #include #include #include #include #include #include #define MID(x,y) ((x+y)>>1)#define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long LL;const int sup = 0x7fffffff;const int inf = -0x7fffffff;int n, m;int no[104];int dp[104][300][300];vector  s,c;void dfs(int p, int condition_num, int condition_amount){    if (p == m){        s.push_back(condition_num);        c.push_back(condition_amount);        //cout << condition_num << endl;        return;    }    dfs(p + 1, condition_num << 1, condition_amount);    if ((condition_num & 3) == 0)        dfs(p + 1, condition_num << 1 | 1, condition_amount + 1);    return ;}int main(){    scanf("%d %d", &n, &m);    mem(no, 0);    for (int i = 1; i <= n; i ++)        for (int j = 1; j <= m; j ++){            char c_tmp;            cin >> c_tmp;            if (c_tmp == 'H')                no[i] += (1 << (m - j));        }    mem(dp, -1);    dp[0][0][0] = 0;    dfs(0, 0, 0);    for (int i = 1; i <= n; i++){        for (int j1 = 0; j1 < (int)s.size(); j1 ++){            if (s[j1] & no[i])          //不能在H处                continue;            for (int j2 = 0; j2 < (int)s.size(); j2 ++){                if (s[j1] & s[j2])      //上面一格                    continue;                for (int j3 = 0; j3 < (int)s.size(); j3 ++){                    if (s[j1] & s[j3])      //上面两格                        continue;                    if (dp[i-1][j2][j3] != -1){                        dp[i][j1][j2] = max(dp[i][j1][j2], dp[i-1][j2][j3] + c[j1]);                    }                }            }        }    }    int res = 0;    for (int j1 = 0; j1 < (int)s.size(); j1 ++){        for (int j2 = 0; j2 < (int)s.size(); j2 ++){            res = max(res, dp[n][j1][j2]);        }    }    printf("%d\n", res);	return 0;}

转载于:https://www.cnblogs.com/AbandonZHANG/archive/2013/03/31/4114230.html

你可能感兴趣的文章