类状压之搜城探宝

题目

思路

看到数据在20以内，果断跑状压，但是由于我太弱了，最后没有调过来，然后在状压的基础上，做了这道题，
按照状压的思路，首先枚举状态，根据题目要求筛去不合法的情况
判断合法的函数（judge）内容

• if(Q(x)！=(k+1))return 0，代表，在房间数大于法宝数的情况下，如果法宝没有全部用完，其所得到的价值绝对没有法宝全部用完得到的价值高，如果用的法宝数大于（k+1）（包括钥匙和传送们），那么绝对不合法
• 用num记录传送们的使用次数，枚举每一个点，判断其父节点是否出现过，

if((!((1<<(fa[i]-1))&x)) && ((1<<(i-1))&x))num++;

如果一个节点在该状态下，但是其父节点不在其中，则到达该节点时使用了传送们，如果num>1即为不合法

• 在筛选后，对剩下的状态求解最大价值即可

附上代码，玄学时间效率

#include<bits/stdc++.h>
using namespace std;
const int maxn=1<<20+1;
int f[25][maxn];
int n,k;
int fa[25],w[25];
int lo[maxn],ans[maxn];
int tot=0;
int lowbit(int x){
    return x&-x;
}
int Q(int x){
    int cnt=0;
    while(x){
        x-=lowbit(x);
        cnt++;  
    }
    return cnt;
}
bool judge(int x){
    if(Q(x)!=(k+1))return 0;
    int num=0;
    for(int i=2;i<=n;i++){
        if((!((1<<(fa[i]-1))&x)) && ((1<<(i-1))&x)){
            num++;
            if(num>1){
                return 0;
            }
        }
    }
    return 1;
}
int main(){
    scanf("%d%d",&n,&k);
    int x,y;
    for(int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        fa[y]=x;
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
        sum+=w[i];
    }
    if(k+1>=n){
        printf("%dn",sum);
        return 0;
    }
    int lim=1<<n;
    for(int i=0;i<lim;i++){
        if(judge(i)){
            lo[++tot]=i;
        }
    }
    int Max=0;
    for(int i=1;i<=tot;i++){
        for(int j=1;j<=n;j++){
            if(lo[i]&(1<<(j-1))){
                ans[i]+=w[j];
            }
        }
        Max=max(Max,ans[i]);
    }
    printf("%dn",Max);
}