本期笔记的内容为状态压缩DP

相关链接：
1.往期笔记： 查看
2.来源：yxc老师的算法提高课

【提高版】DP知识笔记4 有猷 编

例题：

1. 骑士

思路：
贴一个棋盘方便大家手动模拟：

2. 炮兵阵地

思路：

比较烦,给下C++代码（不要走，接下来还有题目）

#include<iostream>
using namespace std;
#define re register
#define Re register
#define MAXN 1050
int n,m,ans,opt[15][MAXN][MAXN],cnt[MAXN],tmp[MAXN];
bool legal[MAXN];
int cont(int x){
    int res = 0;
    while(x){
        res += (x & 1);
        x >>= 1;
    }
    return res;
}
int main() {
    cin >> n >> m;
    for(re int i = 1;i <= n;i++){
        for(re int j = 1;j <= m;j++){
            char ch;
            cin >> ch;
            cnt[i] = cnt[i] * 2 + (ch == 'P');
        }
    }
    for(Re int j = 0;j < (1 << m);j++){
        if((j & (j >> 1)) == 0 && (j & (j << 1)) == 0 && (j & (j << 2)) == 0 && (j & (j >> 2)) == 0)
            legal[j] = true;
        tmp[j] = cont(j);
    }
    for(re int i = 1;i <= n;i++){
        for(re int j = 0;j < (1 << m);j++){
            if(!legal[j] || (j | cnt[i]) != cnt[i])continue;
            for(re int k = 0;k < (1 << m);k++){
                if(!legal[k] || (k | cnt[i - 1]) != cnt[i - 1] || (j & k))continue;
                if(i == 1)opt[i & 1][j][k] = tmp[j];
                ans = max(ans,opt[i & 1][j][k]);
                if(i < 2)continue;
                opt[i & 1][j][k] = 0;
                for(re int l = 0;l < (1 << m);l++){
                    if(!legal[l] || (l | cnt[i - 2]) != cnt[i - 2] || (l & k) || (j & l))continue;
                    opt[i & 1][j][k] = max(opt[!(i & 1)][k][l],opt[i & 1][j][k]);
                }
                opt[i & 1][j][k] += tmp[j];
                ans = max(ans,opt[i & 1][j][k]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

3. 愤怒的小鸟

思路：
比较难，给下C++代码：

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define re register
#define Re register
#define MAXN 1 << 18
#define eps 1e-6
int t,n,m,opt[MAXN],path[25][25];
struct pig{
    double x,y;
}p[25];
void dfs(int st,int cnt){
    if(opt[st] <= cnt)return;
    opt[st] = cnt;
    if(st == (1 << n) - 1)return;
    int tmp = 0;
    for(Re int i = 0;i < n;i++){
        if((st >> i & 1))continue;
        tmp = i;
        break;
    }
    for(re int i = 0;i < n;i++){
        dfs(st | path[tmp][i],cnt + 1);
    }
}
bool cmp(double a,double b){
    if(fabs(a - b) < eps)return true;
    return false;
}
int main() {
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        memset(opt,127,sizeof opt);
        memset(path,0,sizeof path);
        for(Re int i = 0;i < n;i++){
            cin >> p[i].x >> p[i].y;
        }
        if(n == 1){
            cout << 1 << endl;
            continue;
        }
        for(Re int i = 0;i < n;i++){
            path[i][i] = (1 << i);
            for(re int j = 0;j < n;j++){
                if(cmp(p[i].x,p[j].x) ) continue;
                double x1 = p[i].x,y1 = p[i].y,x2 = p[j].x,y2 = p[j].y;
                int cont = 0;
                if(cmp(x1,x2))continue;
                double a = (y1 / x1 - y2 / x2) / (x1 - x2),b,xi;
                b = y1 / x1 - a * x1;
                if(a > 0 || cmp(a,0))continue;
                for(re int k = 0;k < n;k++){
                    xi = p[k].x;
                    if(cmp(p[k].y,a * xi * xi + b * xi))cont += (1 << k);
                }
                path[i][j] = cont;
            }
        }
        dfs(0,0);
        cout << opt[(1 << n) - 1] << endl;
    }
    return 0;
}