AC自动机

POJ 1699 Best Sequence

Posted on

AC自动机+spfa最短路
啊啊,明明AC自动机还有最后一题,今晚怕是写不完了,今天写的还有两道没写题解。

最后一道AC自动机与这一题有相似之处,是这一题的强力加强版本。
先把这题给解决了

题意:
给你很多碱基串,不同碱基串在前后缀相同的条件下可以重叠,要你求出最短的碱基串,包含所有给定串。

思路:
AC自动机上状压SPFA,也可考虑TSP的模型。
还是属于比较基础的,连我都可以不看题解写出来的题目。

#include <cstring>
#include <iostream>
#include <queue>
#include <set>

using namespace std;

const int max_n = 250;
const int max_c = 4;
int key[130];

struct Aho {
    int next[max_n][max_c], fail[max_n], end[max_n];
    int root, size;
    queue<int> que;

    int newNode()
    {
        for (int i = 0; i < max_c; i++)
            next[size][i] = 0;
        end[size++] = 0;
        return size - 1;
    }

    inline void init()
    {
        size = 1;
        root = newNode();
    }

    void insert(int id, const string& str)
    {
        int len = str.length(), now = root;
        for (int i = 0; i < len; i++) {
            int c = key[str[i]];
            if (!next[now][c])
                next[now][c] = newNode();
            now = next[now][c];
        }
        end[now] = 1 << id;
    }

    void build()
    {
        fail[root] = root;
        for (int i = 0; i < max_c; i++)
            if (!next[root][i])
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            if (end[fail[now]])
                end[now] |= end[fail[now]];
            for (int i = 0; i < max_c; i++)
                if (!next[now][i])
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
        }
    }

    int dp[max_n][1024];
    bool inq[max_n][1024];
    void solve(int n)
    {
        memset(dp, 0x3f, sizeof dp);
        memset(inq, false, sizeof inq);
        n = 1 << n;
        que.push(root * n);
        dp[root][0] = 0, inq[root][0] = true;
        while (!que.empty()) {
            int cur = que.front();
            que.pop();
            int a = cur / n, b = cur % n;
            inq[a][b] = false;
            for (int i = 0; i < max_c; i++) {
                int na = next[a][i], nb = b | end[next[a][i]];
                if (dp[na][nb] > dp[a][b] + 1) {
                    dp[na][nb] = dp[a][b] + 1;
                    if (!inq[na][nb]) {
                        inq[na][nb] = true;
                        que.push(na * n + nb);
                    }
                }
            }
        }
        int ans = 0x3f3f3f3f;
        for (int i = 1; i <= size; i++)
            ans = min(ans, dp[i][n - 1]);
        cout << ans << endl;
    }

} aho;

string tmp;
set<string> ks;

int main()
{
    key['A'] = 0, key['C'] = 1, key['T'] = 2, key['G'] = 3;
    ios::sync_with_stdio(false);
    int T, n;
    cin >> T;
    while (T--) {
        ks.clear();
        cin >> n;
        while (n--) {
            cin >> tmp;
            ks.insert(tmp);
        }
        n++;
        aho.init();
        for (set<string>::iterator it = ks.begin(); it != ks.end(); it++)
            aho.insert(n++, *it);
        aho.build();
        aho.solve(n);
    }
    return 0;
}
AC自动机

HDU 3341 Lost’s revenge

Posted on

AC自动机 + 变进制状压DP

看题目的 discuss 都说会卡数据,但我还是 1500ms A了。虽然变进制的思路并不是我的……

最近有点懒得写博客了呀

题意:
还是基因碱基对背景。
给你几个模式串,再给你一个匹配串,允许你对匹配串重新排列,要求重新排列后跟模式串匹配的最大数量。

思路:
如果再加个权值,那就是DP套DP了,(误……
本质上还是一个计数DP,考虑状压,但是给定的匹配串长度上限为 40 ,如果开一个状态+节点的 5维数组,会炸内存。
考虑到将节点的 4 维压缩,因为 40 的实际状态数最多是 4 个碱基数量相同的时候。
也就是\( 10 \times 10 \times 10 \times 10 \),内存与复杂度均可以承受。

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;
const int max_n = 505;
const int max_c = 4;

int num[4];
int change[130];

struct Aho {
    int next[max_n][max_c], fail[max_n], end[max_n];
    int root, size;
    queue<int> que;

    int newNode()
    {
        for (int i = 0; i < max_c; i++)
            next[size][i] = 0;
        end[size++] = 0;
        return size - 1;
    }

    inline void init()
    {
        size = 1;
        root = newNode();
    }

    void insert(char str[])
    {
        int len = strlen(str), now = root;
        for (int i = 0; i < len; i++) {
            int c = change[(int)str[i]];
            if (!next[now][c])
                next[now][c] = newNode();
            now = next[now][c];
        }
        end[now]++;
    }

    void build()
    {
        fail[root] = root;
        for (int i = 0; i < max_c; i++)
            if (!next[root][i])
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            end[now] += end[fail[now]];
            for (int i = 0; i < max_c; i++)
                if (!next[now][i])
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
        }
    }

    int dp[max_n][11 * 11 * 11 * 11 + 5];
    int query()
    {
        int res = 0, bit[4];
        memset(dp, -1, sizeof dp), dp[root][0] = 0;
        bit[3] = 1;
        rrange(i, 1, 3) bit[i - 1] = (num[i] + 1) * bit[i];
        range(A, 0, num[0]) range(T, 0, num[1]) range(C, 0, num[2]) range(G, 0, num[3])
        {
            int sta = A * bit[0] + T * bit[1] + C * bit[2] + G;
            range(cur, root, size - 1) if (dp[cur][sta] >= 0) for (int i = 0; i < 4; i++)
            {
                if (i == 0 && A == num[0]) continue;
                if (i == 1 && T == num[1]) continue;
                if (i == 2 && C == num[2]) continue;
                if (i == 3 && G == num[3]) continue;
                dp[next[cur][i]][sta + bit[i]] = max(dp[next[cur][i]][sta + bit[i]], dp[cur][sta] + end[next[cur][i]]);
            }
        }
        int fnl = 0;
        each(i,4) fnl += num[i] * bit[i];
        range(i,root,size - 1) res = max(res, dp[i][fnl]);
        return res;
    }
} aho;

char buf[50];

int main()
{
    change[(int)'A'] = 0, change[(int)'T'] = 1, change[(int)'C'] = 2, change[(int)'G'] = 3;
    int n, cas = 0;
    while (scanf("%d", &n) != EOF && n) {
        memset(num, 0, sizeof num);
        aho.init();
        for (int i = 0; i < n; i++) {
            scanf("%s", buf);
            aho.insert(buf);
        }
        aho.build();
        scanf("%s", buf);
        int len = strlen(buf);
        for (int i = 0; i < len; i++)
            num[change[(int)buf[i]]]++;
        printf("Case %d: %d\n", ++cas, aho.query());
    }
    return 0;
}
状压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;
}
AC自动机

HDU 2825 Wireless Password

Posted on

AC自动机+状压DP的入门题
虽然不是很好意思,但我的确是先看了kuangbin的代码再敲的。
从AC自动机构建矩阵开始起的出现的那个结点状态,在之后做题中越來越显著。
因为AC自动机本身也没多少地方可以改了,这是一个成熟的算法。而考研我们的运用就只能在理解熟悉它的状态,并运用它的状态。
关于状态应用最明显的就是DP了。

这题之后尽量不看题解……

说了一堆废话,下面放题解。

题意:
有一个长度为 n 的密码,给你一个 m 个字符串的集合。告诉你这个密码必定会包含这集合中的 k 个。
问密码的种数。

思路:
这道题应该是给出一个状态就很好理解了。
开一个三维数组,记 \( dp\left[ i \right] \left[ j \right] \left[ k \right] \) 为长度为 \( i \) ,在第\( j \) 个结点,含有字符串数量的状态为 \( k \) 的可构字符串数量。
每次在AC自动机上跑的时候更新一下状态,最后再将包含字符串数量大于等于 k 的状态数量累加即可。

相信我,真的是入门级的……

AC Code

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

using namespace std;

typedef unsigned long long ull;

const int mod = 20090717;
const int max_n = 110;
const int max_c = 26;
char buf[max_n];

int n, m, k;

struct Aho {
    int next[max_n][max_c], fail[max_n], end[max_n];
    int root, size;
    queue<int> que;

    int newNode()
    {
        for (int i = 0; i < max_c; i++)
            next[size][i] = -1;
        end[size++] = 0;
        return size - 1;
    }

    inline void init()
    {
        size = 0;
        root = newNode();
    }

    inline void insert(char str[], int id)
    {
        int len = strlen(str), now = root;
        for (int i = 0; i < len; i++) {
            int c = str[i] - 'a';
            if (next[now][c] == -1)
                next[now][c] = newNode();
            now = next[now][c];
        }
        end[now] = 1 << id;
    }

    void build()
    {
        fail[root] = root;
        for (int i = 0; i < max_c; i++)
            if (next[root][i] == -1)
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            end[now] |= end[fail[now]];
            for (int i = 0; i < max_c; i++)
                if (next[now][i] == -1)
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
        }
    }

    int dp[max_c + 2][max_n][1 << 10];

    int solve()
    {
        int ans = 0, ni, nj, ns;
        memset(dp, 0, sizeof dp), dp[0][0][0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < size; j++)
                for (int state = 0; state < (1 << m); state++)
                    if (dp[i][j][state]) {
                        for (int x = 0; x < max_c; x++) {
                            ni = i + 1, nj = next[j][x], ns = state | end[nj];
                            dp[ni][nj][ns] = (dp[ni][nj][ns] + dp[i][j][state]) % mod;
                        }
                    }
        for (int state = 0; state < (1 << m); state++) {
            if (__builtin_popcount(state) < k)
                continue;
            for (int i = 0; i < size; i++)
                ans = (ans + dp[n][i][state]) % mod;
        }
        return ans;
    }
} aho;

int main()
{
    while (scanf("%d %d %d", &n, &m, &k) != EOF) {
        if (n == 0 && m == 0 && k == 0)
            break;
        aho.init();
        for (int i = 0; i < m; i++) {
            scanf("%s", buf);
            aho.insert(buf, i);
        }
        aho.build();
        printf("%d\n", aho.solve());
    }
    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;
}