状压DP

HDU 4628 Pieces

Posted on

CLS的状压DP系列……
然而实际上也算是一道简单题,但是我并没有立刻写出来。
不知道为什么,每次我尝试这用已知最优状态去推其他状态都是错的……
然而用当前状态之前的状态来推当前状态却是对的。

顺便学习了一个,二进制子集的枚举方法。for ( int sta = state ; sta ; sta = (sta - 1) & state )
学了这么久状压居然连这个都知道真是醉了……

题意:
给你一个字符串,每次只能取走一个回文串,问最少取几次。

思路:
先预处理出所有状态是否为回文串,并使得 这个状态取值为 1 。
枚举每个状态,再枚举它的所有子集。
状态转移方程 为 dp[sta] = min(dp[sta], dp[sta ^ s] + dp[s] )

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 16;
const int inf = 0x3f3f3f3f;

char str[maxn];
int dp[1 << maxn];
int len;

void judge(int sta)
{
    if (dp[sta] != inf)
        return;
    int l = 0, r = len - 1;
    while (l < r) {
        while ((sta & (1 << l)) == 0 && l < len - 1)
            l++;
        while ((sta & (1 << r)) == 0 && r > 0)
            r--;
        if (str[l] != str[r]) {
            dp[sta] = inf + 1;
            return;
        }
        l++, r--;
    }
    dp[sta] = 1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", str);
        len = strlen(str);
        int maxs = (1 << len) - 1;
        fill(dp, 0x3f), dp[0] = 0;
        range(sta, 1, maxs) each(j, len) judge(sta | (1 << j));
        range(sta, 1, maxs)
        {
            for (int s = sta; s; s = (s - 1) & sta)
                dp[sta] = min(dp[sta], dp[sta ^ s] + dp[s]);
        }
        printf("%d\n", dp[maxs]);
    }
    return 0;
}
状压DP

BZOJ 4197 寿司晚宴

Posted on

上一场多校一道状压DP的原题。
那我肯定是去做原题啦。

多校的时候我还觉得这肯定是许学姐的锅,没想到居然能转化成状压。

题意:
中文题面,给你\( [ 2, n ] \) 这几个数,要你各找两组数字,两组数字之间两两互质。
\( n\) 最大为500,问组合数量。

思路:
考虑数据 \( n\) 非常小,在 \( \sqrt 500 \)以内的质数只有8个,而大于\( \sqrt 500 \)的大元素只可能为一个,那么我们把相同的大元素放在一起处理,开一个二维数组表示这个大元素在两组中的哪一组,而对于小元素,可以用状态压缩来表示两组数字各自包含那几个质数。最后累加的时候让两个状态不重叠即可。

代码中 \( dp [ k ] [ a ] [ b ] [ c ] \) 表示 前\( k\)个元素中 第一组数包含的小质数状态为\( a\) ,第二组数包含的小质数状态为\( b\) ,大质数为在第一组\( 0\) ,或者在第二组\( 1\) 的组合数量。
dp过程中,可以通过类似背包处理,反向计算,省掉一维。

\( f [ k ] [ a ] [ b ] \) 表示前\(k \) 个元素中,第一组包含的小质数状态为\( a\),第二组包含的小质数状态为 \( b\) 的组合数量。

因为\( dp\)数组包含了当前大质数的分配状态。所以在处理不同大质数的时候理所当然地要将 \( dp\)数组重置。方法就是用\( f [ a ] [ b ] \)进行汇总,再分配。
在汇总的时候格外要注意的是,必须减去一个以前的\( f [ a ] [ b ] \),因为 \( dp\)数组在大质数分配的两个状态中都记录了以前的\( f [ a ] [ b ] \),也就是在此之上没有加上任何元素的组合数。汇总的时候是多加一次的,这应该比较容易理解。

而状态转移方程是最好理解,我就不多说了 虽然不是我想出来的

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int maxn = 510;
const int maxc = 1 << 8;

ll dp[maxc][maxc][2], f[maxc][maxc];
ll n, mod;
int pri[10] = { 2, 3, 5, 7, 11, 13, 17, 19, 0, 0 };

struct node {
    int state;
    int big;
    bool operator<(const node& a) const { return big < a.big; }
} num[maxn];

void init()
{
    range(i, 2, n)
    {
        int x = i, v;
        each(j, 8) if (x % (v = pri[j]) == 0)
        {
            while (x % v == 0)
                x /= v;
            num[i].state |= (1 << j);
        }
        num[i].big = x;
    }
    sort(num + 2, num + n + 1);
    f[0][0] = 1;
}

int main()
{
    scanf("%lld %lld", &n, &mod);
    init();
    range(i, 2, n)
    {
        if (i == 2 || num[i].big == 1 || num[i].big != num[i - 1].big)
            reach(j, maxc) reach(k, maxc) dp[j][k][0] = dp[j][k][1] = f[j][k];
        reach(j, maxc) reach(k, maxc)
        {
            if ((num[i].state & j) == 0)
                dp[j][k | num[i].state][1] = (dp[j][k | num[i].state][1] + dp[j][k][1]) % mod;
            if ((num[i].state & k) == 0)
                dp[j | num[i].state][k][0] = (dp[j | num[i].state][k][0] + dp[j][k][0]) % mod;
        }
        if (i == n || num[i].big == 1 || num[i].big != num[i + 1].big)
            reach(j, maxc) reach(k, maxc) f[j][k] = (dp[j][k][0] + dp[j][k][1] - f[j][k] + mod) % mod;
    }
    ll ans = 0;
    reach(i, maxc) reach(j, maxc) if ((i & j) == 0) ans = (ans + f[i][j]) % mod;
    printf("%lld\n", ans);
    return 0;
}
状压DP

状压DP 再入门 !!!

Posted on

昨天写状压DP被煞笔天海和死肥宅带鱼嘲笑了

Damn!

然而事实也是一些状压DP的经典问题我还不会……
更烦人的是今天的多校是DP专场,AC自动机+DP 这个倒是常见的套路 树形DP ,反背包DP,树上匹配+DP,各种姿势的DP……

老实说,我的DP是很弱的……连背包问题上的我个人觉得都不是很熟练……

这里写一下状压DP入门的三道题,三道题其实差不了多少,但在难度上基本上是循序渐进的。

POJ 3254 Corn Fields

题意:
给你一个矩阵,让你种一些玉米,要求只能在给定的格子上种,并且相邻的格子不能同时存在玉米。
问方案数。

思路:
首先在输入的时候记录一下每一行不可种植的格子,将它压缩为二进制。
再是筛选出在同一行满足条件的所有状态,因为不能存在相邻格子,也就是 \( i \& ( i << 1 ) = 0 \)

枚举每一行满足条件的所有状态,进而枚举下一行满足条件的所有状态,当 \( state[i] \& state[j] ==0 \)时,就表示上下状态的玉米不会相邻,这两行是满足题意的,所以只要将当前状态的数量加到下一行的状态中。

最后将最后一行的所有状态数相加即为我们要求的答案。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int maxn = 20;
const int maxm = 5000;
const int mod = 1e8;

int dp[maxn][maxm];
int val[maxn], state[maxm];

int main()
{
    int n, m, top, v;
    while (scanf("%d %d", &n, &m) != EOF) {
        fill(dp, 0), fill(val, 0), top = 0;
        each(i, n) each(j, m)
        {
            scanf("%d", &v);
            v ? 0 : val[i] += (1 << (m - j - 1));
        }
        each(i, (1 << m)) if (!(i & (i << 1))) state[top++] = i;
        each(i, top) if (!(state[i] & val[0])) dp[0][i] = 1;
        range(i, 1, n - 1) each(j, top)
        {
            if (state[j] & val[i])
                continue;
            each(k, top)
            {
                if (state[k] & val[i - 1])
                    continue;
                if (state[j] & state[k])
                    continue;
                dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
            }
        }
        range(i, 1, top - 1) dp[n-1][0] = (dp[n-1][0] + dp[n-1][i]) % mod;
        printf("%d\n", dp[n-1][0]);
    }
    return 0;
}

POJ 1185 炮兵阵地

题意:
题意基本和上一题一致,不过不能同时放置的范围从一个长度为 \( 1 \) 的 十字,增大 到长度为 \( 2 \) 的十字。

问能放置的最大数量。

思路:
思路基本一致,不过存储状态数几何倍上升,需要记录两行的状态,用当前的两行去枚举判断下面的两行。判断一下可行性后,将两个状态的数量比较一下即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int maxn = 110;
const int maxm = 70;
const int mod = 1e8;

int dp[maxn][maxm][maxm];
int val[maxn], state[maxm], soldier[maxm];
int n, m, top, v;

char buf[15];

int main()
{
    scanf("%d %d", &n, &m);
    each(i, n)
    {
        scanf("%s", buf);
        each(j, m) if (buf[j] == 'H') val[i] += (1 << (m-j-1) );
    }
    each(i, (1 << m)) if ((i & (i << 1) || (i & (i << 2)))) continue;
    else soldier[top] = __builtin_popcount(i), state[top++] = i;
    each(i, top) if (!(state[i] & val[0])) dp[0][i][0] = soldier[i];
    each(i, top) if (!(state[i] & val[1]))
    {
        each(j, top) if (!(state[j] & val[0]) && !(state[i] & state[j]))
        {
            dp[1][i][j] = max(dp[1][i][j], dp[0][j][0] + soldier[i]);
        }
    }
    range(r, 2, n - 1) each(i, top) if (!(state[i] & val[r]))
    {
        each(j, top) if (!(state[j] & val[r - 1]) && !(state[i] & state[j]))
        {
            each(k, top) if (!(state[k] & val[r - 2]) && !(state[j] & state[k]) && !(state[i] & state[k]))
            {
                dp[r][i][j] = max(dp[r][i][j], dp[r - 1][j][k] + soldier[i]);
            }
        }
    }
    int ans = 0;
    each(i, top) each(j, top) ans = max(ans, dp[n - 1][i][j]);
    printf("%d\n", ans);
    return 0;
}

HDU 4539 郑厂长系列故事——排兵布阵

题意:
这道题和上一题几乎如出一辙,只是同时放置的范围再次改变了……
从一个大十字变成了 曼哈顿距离不超过 \( 2 \)的范围。

注: 两点 \( \left( x_0, y_0 \right) \) 与 \( \left( x_1 , y_1 \right) \) 曼哈顿距离 为 \( \left| x_0 - x_1 \right| + \left| y_0 - y_1 \right| \)

思路:
一个思路,只是判断可行性的时候有点不一样罢了……

比较建议上一题学着敲,这道自己敲。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int maxn = 110;
const int maxm = 205;

int dp[maxn][maxm][maxm];
int val[maxn], state[maxm], soldier[maxm];
int top, v, row, col;

bool check(int a, int b) { return (a & (b << 1)) == 0 && (a & (b >> 1)) == 0; }

int main()
{
    while (scanf("%d %d", &row, &col) != EOF) {
        if (row == 0 || col == 0) {
            puts("0");
            continue;
        }
        fill(dp, 0), fill(val, 0), top = 0;
        each(i, row) each(j, col)
        {
            scanf("%d", &v);
            v ? 0 : val[i] += 1 << (col - j - 1);
        }
        each(i, (1 << col)) if (!(i & (i << 2))) soldier[top] = __builtin_popcount(i), state[top++] = i;
        each(i, top) if (!(state[i] & val[0])) dp[0][i][0] = soldier[i];
        each(i, top) if (!(state[i] & val[1]))
        {
            each(j, top) if (!(state[j] & val[0]) && check(state[i], state[j]))
            {
                dp[1][i][j] = max(dp[1][i][j], dp[0][j][0] + soldier[i]);
            }
        }
        range(r, 2, row - 1) each(i, top) if (!(state[i] & val[r]))
        {
            each(j, top) if (!(state[j] & val[r - 1]) && check(state[i], state[j]))
            {
                each(k, top) if (!(state[k] & val[r - 2]) && check(state[k], state[j]) && (state[k] & state[i]) == 0)
                {
                    dp[r][i][j] = max(dp[r][i][j], dp[r - 1][j][k] + soldier[i]);
                }
            }
        }
        int ans = 0;
        each(i, top) each(j, top) ans = max(ans, dp[row - 1][i][j]);
        printf("%d\n", ans);
    }
    return 0;
}
状压DP

CodeForces 11D A Simple Task

Posted on

今天做的不太一样的状压,从去年的专题找的,看到学长并没有写是已经写过了么?
可能是因为跟图论相关的原因吧。

题意:
给你一个简单图,让你找出简单环的数量。
附 : 简单环就是没有重边和重点的环。
点数为 19 。

思路:
19个点,一般很容易想到状压和二维……根据数据猜算法?
事实上我是没有想到二维的

dp[ s ] [ p ] 表示 s 集合 p 为当前位置的边数 ,初始对每个状态 dp [ 1<< i ][ i ] 设置为 1
对于每一个状态,固定的从最小的一位 1 作为起点,从这个起点开始扩散,如果能回到这个起点,就进行计数。

因为对于一个环,枚举起点和终点的话,会存在起点到终点,和以终点为起点的情况。
比如说 1-> 2 -> 3 ->1 和 3 -> 2 -> 1 -> 3

AC Code

#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 20;
typedef long long ll;

int map[maxn][maxn], n, m, u, v;
ll dp[1 << maxn][maxn];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        u--, v--;
        map[u][v] = map[v][u] = 1;
    }
    ll ans = 0;
    for (int i = 0; i < maxn; i++)
        dp[1 << i][i] = 1;
    for (int st = 1; st < (1 << n); st++) {
        int s = __builtin_ctz(st); //右边第一个1的位置
        for (int e = s; e < n; e++) {  //枚举集合元素 作为当前位置
            if (st & (1 << e)) {
                for (int i = s; i < n; i++) {  // 扩散状态
                    int nst = st | (1 << i);
                    if (map[e][i] && (st & (1 << i)) == 0) { //新状态
                        dp[nst][i] += dp[st][e];
                        if (map[i][s] && __builtin_popcount(nst) > 2) // 能回到起点 1的数量也就是边数大于2
                            ans += dp[st][e]; 
                    }
                }
            }
        }
    }
    printf("%lld\n", ans / 2);
    return 0;
}

状压DP

CodeForces 8 C Looking for Order

Posted on

前几天刚写了一道状压DP入门题,结果这次就遇到了,在比赛最后一点时间一眼看破,无奈只有想法,写不来……

不过赛后尝试写的时候遇到了一个自己不会的问题,也就是说假如比赛的时候开了这道题,我也会一直卡着。

题意:
给你很多个行李的位置和起点的位置,要你把所有行李搬运到起点,一次只能搬一个或者两个,花费是距离,求最小花费。行李最多24个。

思路
状压dp,对于每一个状态,我们通过dp维护其最优。
因为这里的拿取行李是与顺序无关的,那么,我通过从小到大枚举状态,在保证我当前状态最优的前提下,由我当前状态拓展而来的状态只要通过比较就可以达到最优好暴力
所以我通过枚举,找到第一个它能够搬运的行李,每次都拓展这个状态即可。

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int max_n = 30;
const int max_m = 1 << 24;

int n, tmp;
int dp[max_m], pre[max_m];

pii nodes[max_n];
int dis[max_n][max_n];

inline int calcul(int a, int b)
{
    return (nodes[a].first - nodes[b].first) * (nodes[a].first - nodes[b].first) + (nodes[a].second - nodes[b].second) * (nodes[a].second - nodes[b].second);
}

int main()
{
    scanf("%d %d %d", &nodes[29].first, &nodes[29].second, &n);
    nodes[n] = nodes[29];
    each(i, n) scanf("%d %d", &nodes[i].first, &nodes[i].second);
    each(i, n + 1) range(j, i + 1, n) dis[i][j] = dis[j][i] = calcul(i, j);
    fill(dp, 0x3f), dp[0] = 0;
    each(i, (1 << n)) if (dp[i] != inf) each(j, n) if (!(i & (1 << j)))
    {
        int t = (i | (1 << j));
        if (dp[t] > (tmp = dp[i] + 2 * dis[j][n])) {
            dp[t] = tmp;
            pre[t] = i;
        }
        each(k, n) if (!(t & (1 << k)))
        {
            int p = (t | (1 << k));
            if (dp[p] > (tmp = dp[i] + dis[k][n] + dis[j][n] + dis[k][j])) {
                dp[p] = tmp;
                pre[p] = i;
            }
        }
        break ;
    }
    int cur = (1 << n) - 1, ps, det;
    printf("%d\n0 ", dp[cur]);
    while (cur != 0) {
        ps = pre[cur];
        det = cur - ps;
        each(i, n) if (det & (1 << i)) printf("%d ", i + 1);
        printf("0 ");
        cur = ps;
    }
    return 0;
}
状压DP

HDU 1074 Doing Homework

Posted on

虽然可以算得上是道水题,但作为我第一道状压DP,还是把它写入我的博客。
觉得这道题作为入门题是极好的,比网上说的什么矩阵的好理解的多!!
因为几乎只涉及了状压

特别想感慨一句,dp真的是个优美的暴力啊……

题意:
有几门课的作业,分别给出截止时间,完成所需时间,没拖一天扣一分,问最少扣多少分,并输出写作业顺序。

思路:
总的思路是对于每一个状态,都进行课程的枚举,并计算花费时间,拖作业时间,从而进行状态转移,每次状态转移都使拖作业的时间最小即可。
不是暴力??但是真的很优美!
课程数很小,只有15门,因此状压无压力。

AC Code

#include <cstdio>
#include <cstring>
#include <numeric>
#include <queue>
#include <stack>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

const int max_n = 16;
const int max_m = 110;

int n;
bool vis[1<<max_n];

struct co {
    int deadline, cost;
    char name[max_m];
} course[max_n];

struct p {
    int cost, bey, pre;
} dp[1 << max_n];

void output(int state)
{
    if (!state)
        return;
    output(dp[state].pre);
    int idx = state ^ dp[state].pre, pos = 0;
    while ((idx & 1) == 0)
        idx >>= 1, pos++;
    puts(course[pos].name);
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        fill(vis, false);
        each(i, n) scanf("%s %d %d", course[i].name, &course[i].deadline, &course[i].cost);
        int en = (1 << n);
        each(i, en) each(j, n)
        {
            int j2 = (1 << j);
            if (!(i & j2)) {
                int cur = i | j2;
                dp[cur].cost = dp[i].cost + course[j].cost;
                int bey = (dp[cur].cost > course[j].deadline ? dp[cur].cost - course[j].deadline : 0) + dp[i].bey;
                if (!vis[cur] || bey < dp[cur].bey)
                    vis[cur] = true, dp[cur].bey = bey, dp[cur].pre = i;
            }
        }
        printf("%d\n", dp[en - 1].bey);
        output(en - 1);
    }
    return 0;
}