状压DP复盘

1.预处理合法状态：https://www.acwing.com/problem/content/1066/

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
ll dp[12][2050][102];//dp[i][j][k]表示第i行放了j的模样用了k个的方案数
int cnt[2049];
vector<int> state;
vector<int> h[3000];
int count(int x){
    int cn=0;
    for(int i=n+1;i>=0;i--){
        if(((x>>i)&1)==1) cn++;
    }
    return cn;
}
bool check(int i){
    for(int j=n-1;j>=0;j--){
        if(((i>>j)&1)&&((i>>(j+1))&1)){
            return 0;
        }
    }
    return 1;
}
int main(){
    cin>>n>>k;
    dp[0][0][0]=1;
    //预处理
    for(int i=0;i<(1<<n);i++){
        if(check(i)) state.push_back(i);
    }
    for(int i=0;i<state.size();i++){
        for(int j=0;j<state.size();j++){
            int a=state[i],b=state[j];
            if(((a&b)==0)&&(check(a|b))){
                h[i].push_back(j);
            }
        }
    }
    for(int i=1;i<=n+1;i++){
        for(int j=0;j<=k;j++){
            for(int w=0;w<state.size();w++){
                for(int s=0;s<h[w].size();s++){
                    int kk=count(state[w]);
                     if(kk>j) continue;
                    else{
                        dp[i][state[w]][j]+=dp[i-1][state[h[w][s]]][j-kk];
                    }
                }
            }
        }
    }
    cout<<dp[n+1][0][k];
}

2.数学+状压DP：https://www.acwing.com/problem/content/526/

（用集合思想去理解DP确实清楚不少QAQ）

首先，看到数据范围不难想到状压DP，我们用dp[i]表示在状态i下最少用多少炮弹。

dp[0]=0，我们就是求dp[(1<<n)-1]。

接下来考虑具体的转移：

我们计f[i][j]表示经过i,j点的抛物线所有经过点的状态。

我们看看i的样子:假如是1010100，说明还需要把1,2,4,6的位置上的🐖击落。于是我们可以对于这4个点选2个或者1个击落（当然实际可能不止），同时，不能选f[i][j](i,j位置已经击落的，因为可以优化（具体可以见洛谷第一个题解））。

其次，一般的dp转移都是根据已有推出现在的状态，但是这题比较难实现，我们考虑另一种等价：根据现在去更新将来，具体的,f[0]=0的基线条件一定正确，对于从小到大枚举到的i,当我们取f[i]时，f[i]的值一定是正确的（具体的，假如i=10010，那么要可以转移到它的也只有10000,00010，00000,而他们是正确的，同时他们根据击落的所有情况对将来更新，因此f[i]一定是正确的）

因此，我们得到策略：枚举i,j，让dp[cur|f[i][j]]=min(dp[cur|f[i][j],dp[cur]+1)，同时除了两个的我们还要考虑击落一个：|f[i][i]即可。

这样得到的时间复杂度：n*n*2^n。

事实上我们可以优化到n*2^n:

我们考虑这n个Pig，我们不妨随便给他们标号1，2，3.到n，那么决定答案的是每一次选择的是什么而非按什么顺序，于是我们可以固定一个规则：对于没有打落的，只能打落最靠前的。

也就是题目又加了一个条件：从前往后打。

把这条件用到状态转移上:我们假设i的最低位0是第k个，我们只用枚举f[k][w]（w从1--n）即可。

此时相比原来的DP：中间过程可能结果不一样，但是dp[n]都表示打落n只pig的最少次数（答案不随打落顺序变化），于是就可以降一个n愉快的AC了。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
double eps=1e-6;
int t,n,m;
struct node{
    double x,y;
}h[20];
int ans;
int inff=0x7f7f7f7f;
int f[20][20];//f[i][j]表示经过i与j的状态
int cmp(double x,double y){
    if(fabs(x-y)<eps) return 1;
    return 0;
}
int dp[1000100];//dp[i]表示处理到状态i时的最少步数
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>h[i].x>>h[i].y;
        //预处理
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++){
            f[i][i] = 1<<(i-1);
            for(int j=1;j<=n;j++){
                double x1=h[i].x,x2=h[j].x,y1=h[i].y,y2=h[j].y;
                if(cmp(x1,x2)==1) continue;
                double a=(y1/x1-y2/x2)/(x1-x2);
                double b=(y1/x1-a*x1);
                
                if(a>0||cmp(a,0.0)) continue;
                for(int k=1;k<=n;k++){//注意顺序
                    if(cmp(a*h[k].x*h[k].x+b*h[k].x,h[k].y)!=1) continue;
                    f[i][j]+=(1<<(k-1));
                }
            }
        }
        //DP
        memset(dp,0x3f,sizeof(dp));
        dp[0]=0;
        for(int i=0;i<(1<<n);i++){
            int k=0;
            for(int j=0;j<=n-1;j++){
               if(((i>>j)&1)==0){
                    k=j+1;
                    break;
                }
            }
            for(int w=1;w<=n;w++){
                int xx=f[w][k];
                dp[xx|i]=min(dp[xx|i],1+dp[i]);
            }
        }
        cout<<dp[(1<<n)-1]<<endl;
    }
}