NOIP专题复习（三） 状压DP学习笔记

其实并不是三，已经走了很多专题了。
之后慢慢填坑吧。

---

我觉得学普通的DP已经救不了我了。
发觉似乎NOIP状压蛮裸的（flag立的飞起），于是学一波。

其实在下作为一只蒟蒻，认为状压DP属于很好理解但不太好写的类型。
还是从经典例题互不侵犯开始。

luogu1896 互不侵犯

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
1 <=N <=9, 0 <= K <= N * N

在下大致将学习这道题做法步骤拆分如下。
1，数据范围是识别状压DP的标志。
这个数据范围，一般来说是状压DP。

2，位运算是进行状压DP的主力武器。
很多教程都会直接讲一下四个运算符是什么意思，然后直接上代码。
在下觉得有点不太友好啊orz。毕竟大家都知道这是什么意思，只是不会写而已。
首先对于这道题，用到的位运算大致解析如下：
假设现在某一行状态为i，i的对应的二进制数，某一位是1表示这一位放棋子，是0表示不放。
那么分别来看这样几种情况：
1）左右相邻

如图，这里举了两个例子，分别没有左右相邻和有相邻的情况。显而易见的，如果a&(a>>1)=0，就表示这一种方法是合法的，否则就不合法。

2）上下相邻
这个还是蛮好理解的。如果a&b=0，就表示状态a的每一位都和下一位都不冲突。

3）对角相接
>>1的本身含义就是将所有位向右移。那么如果a，b对角线上是相接的，我们发现：
(a>>1) & b = 0表示不在右下方，(a<<1) & b表示不在左下方。
例如：

我们看到，黄色的在位运算之后与红色的产生了冲突，不合法了。

4）判断有多少放过
接下来还要用到统计某一行一共放过多少王的小函数。这一函数的实现原理很简单：

while( x不为0 )
    x右移一位
    if(现在末位是1) 
        数量+1
    end if
end while

而末位是1可以用x & 1快速解决。
但这样是比较慢的。有一个黑科技：lowbit(x) = x & (-x) ，这个东西可以取出二进制下第一位不为0的数，原理各位请去查树状数组。那么这个代码可以这么写：

while(x不为0)
    数量+1
    x -= lowbit(x)
end while

亲测可以把8ms变成4ms。

3，行之间转移是状压DP的本质
有了这些基础，接下来就方便理解很多。
转移方程：

dp[i][j][s]=∑o|o与s不冲突dp[i−1][j−k][o]，k为s状态放过的王的数量

这一状态维护的是第i行放了j个王，状态为s所得到的方案数之和。
实现上，我们可以遍历维护每一种状态，这样复杂度O(n2k22n)
再来想想能不能简化一些枚举次数——当然是可以的。
如果朴素算法的话，我们需要首先判断每一种状态是否左右相邻，这实际上是一种非常浪费的行为，那么我们就可以加一次预处理，枚举出所有符合条件可以转化的状态，同时处理出其数量.
那么经过预处理的东西就是所有可能的状态数。由此，我们可以写出其预处理：
dp[1][many[i]][i]=1，用一个con数组维护可能状态，many数组维护某一状态有多少放过。
总复杂度O(2n+n2kcnt2)
最后的问题就是一共有多少可能的状态，显然是2n−1种。而这其中有多少符合条件的呢？开大点并不亏。在下开到了103就过了。

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
#define INF 1<<8-1
LL n, m;
LL con[103], many[103], cnt;
LL dp[10][90][103], ans;
LL getnum(LL x) {
    int qwq = 0;
    while(x != 0) {
        ++qwq;
        x = x - (x & (-x));
    }
    return qwq;
}
bool check(LL a, LL b) {
    if(a & b) return 1;
    if((a >> 1) & b) return 1;
    if((a << 1) & b) return 1;
    return 0;
}
int main() {
    scanf("%d%d", &n, &m);
    for(LL i = 0; i <= (1 << n) - 1; ++i) {
        if((i & (i >> 1))  == 0) {
            ++cnt;
            con[cnt] = i;
            many[cnt] = getnum(i);
        }
    }
    LL s, o, sl;
    for(int i = 1; i <= cnt; ++i) dp[1][many[i]][i] = 1;
    for(int i = 2; i <= n; ++i) {
        for(int j = 0; j <= m; ++j) {
            for(int k = 1; k <= cnt; ++k) {
                s = con[k]; sl = many[k];
                if(sl > j) continue;
                for(int l = 1; l <= cnt; ++l) {
                    o = con[l];
                    if(check(s, o)) continue;
                    dp[i][j][k] += dp[i-1][j-sl][l];
                }
            }
        }
    }
    for(int i = 1; i <= cnt; ++i) ans += dp[n][m][i];
    cout<<ans<<endl;
    return 0;
}

---

luogu1789 玉米田

套路性很强的，来看玉米田。
数据范围->12，状压，别犹豫。
再来看转移，这题似乎比互不侵犯还要简单一些，因为没有数量限制。
因此这里的状态可以直接设为dp[i][s]表示第i行状态为s，那么

dp[i][s]=∑o，s不冲突dp[i−1][o]

注意一点，不能放的限制条件我们用这个东西维护：
canput[i] = (canput[i] << 1) | (can ^ 1)
它表示第i行符合条件时的状态，而每一位为1代表这一位不能放，以方便我们的&操作。
|可以方便的加上一个东西。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long LL;
#define mod 100000000
LL n, m;
LL con[2003], many[2003], cnt; 
LL dp[15][2003], ans;
inline LL lowbit(LL x) {
    return x & (-x);
}
inline LL check(LL o, LL s) {
    if(o & s) return 1;
    else return 0;
}
LL canput[15];
int main() {
    scanf("%d %d", &n, &m);
    int can;
    LL inf = (1 << m) - 1;
    for(int i = 1; i <= n; ++i) {
        canput[i] = 0;
        for(int j = 1; j <= m; ++j) {
            scanf("%d", &can);
            canput[i] = (canput[i] << 1) | (can ^ 1); 
        }
    }
    for(LL i = 0; i <= inf; ++i) {
        if((i & (i >> 1)) == 0) 
            ++cnt, con[cnt] = i;
    }
    int len;
    for(int i = 1; i <= cnt; ++i) {
        if(con[i] & canput[1]) continue;
        dp[1][i] = 1;
    }
    for(int i = 2; i <= n; ++i) {
        for(int k = 1; k <= cnt; ++k) {
            LL s = con[k];
            if(s & canput[i]) continue;
            for(int l = 1; l <= cnt; ++l) {
                LL o = con[l];
                if(o & canput[i - 1]) continue;
                if(check(o, s)) continue;
                dp[i][k] += dp[i-1][l];
            }
        }
    }
    for(int i = 1; i <= cnt; ++i) {
        ans = (ans + dp[n][i]) % mod;
    } 
    cout<<ans<<endl;
    return 0;
}

---

以上两道题揭示了这类摆放问题的基本套路：先枚举预处理，然后判断符合条件逐层转移。现在来思考这一经典问题的两种变形
1）如果现在要求相邻空出来的数量为2怎么办？
每次转移的时候加一层判断，判断上上行是否满足，而预处理稍微加一点变化即可。

2）最优化，一个棋盘最多能放多少？
可以这么写：dp[i][s]=max{dp[i−1][o]}+getnum(s)维护第i行状态为s时取到的最值。

---

luogu2883/NOIP2016D2T3 愤怒的小鸟

先和我默念：辣鸡愤怒的小鸟，毁我青春，毁我人参！
这个题数据范围有一个m是用来给暴力选手的，可以无视（并不）
这是一道长的不像我们刚才看到的状态压缩题的状压题，其转移方程很有趣：
dp[S]=min{dp[S′]}+1|S′∈S且∀(x,y)∈S′有atx2+btx=y
换句话说，就是选取最小的集合进行转移。
那么这道题就可以分成这么几个部分：
1）枚举每个集合并保存之
2）对于每种情况进行状态压缩搞
对于1，我们开一个query[i][j]数组维护包含ij两个点达到的值
对于2，注意两件事：一个是每次转移状态可以只对第一头没有打死的猪进行讨论，这样是没有后效性的，因为这头猪迟早要被打死；另一个是我们需要讨论对这一状态转移是单独打这一头还是连带打一堆。
这道题集合的处理也是够恶心的。首先我们用一个set[i][j]数组维护过ij两点的集合可以经过的小鸟，这里要先解个方程。但这道题的坑点是，因为是抛体运动，a一定小于0，并且由于重力的影响，小鸟是不可能做直线运动的。
调了4个小时终于A了，真绝望。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
typedef double db;
typedef long long LL;
#define EPS 0.0000001
#define INF 1<<20
LL dp[INF], set[20][20];
db torix[20], toriy[20];
int n, qinli;
bool equal(db a, db b) {
    return fabs(a - b) < EPS;
}
inline bool getab(db x1, db y1, db x2, db y2, db &a, db &b) {
    if(equal(x1, 0) && (!equal(x2, 0))) b = 0, a = y2 / (x2 * x2);
    else if(equal(x2, 0) && (!equal(x1, 0))) b = 0, a = y1 / (x1 * x1);
    else if(equal(x1, 0) && equal(x2, 0)) return false;
    else {
        a = (y1*x2-x1*y2)/(x1-x2)/x1/x2;
        b = (y1-a*x1*x1) / x1;
        if(a > 0) return false;
        else if(a * b > 0) return false;
        else return true;
    }
}
inline bool isin (db a, db b, db x, db y) {
    return equal(a * x * x + b * x , y);
}
void init() {
    cin>>n>>qinli;
    db atmp, btmp, ftmp;
    LL now;
    memset(set, 0, sizeof(set));
    memset(dp, 0x3f, sizeof(dp));
    for(int i = 1; i <= n; ++i) dp[i] = INF;
    for(int i = 1; i <= n; ++i) cin>>torix[i]>>toriy[i];
    for(int i = 1; i <= n; ++i) 
        for(int j = i + 1; j <= n; ++j) {
            if(getab(torix[i], toriy[i], torix[j], toriy[j], atmp, btmp)) {
                for(int t = 1; t <= n; ++t) {
                    if(isin(atmp, btmp, torix[t], toriy[t]))
                        set[i][j] |= (1<<(t - 1));
                } 
            }
        }
}
void work() {
    LL s, o;
    LL inf = (1 << n) - 1;
    dp[0] = 0;
    for(int i = 0; i <= inf; ++i) {
        s = i, o = 1;
        while(s & 1) s >>= 1, ++o;
        dp[i | (1 << (o - 1))] = min(dp[i | (1 << (o - 1))], dp[i] + 1);
        for(int j = o + 1; j <= n; ++j) 
            if(set[o][j])
                dp[i | set[o][j]] = min(dp[i | set[o][j]], dp[i] + 1);  
    }   
    cout<<dp[(1 << n) - 1]<<endl;
}
int main() {
    int T; cin>>T;
    while(T--) {
        init();
        work();
    }
}