abc 319 f （ 状压dp + 树上bfs

#include 
using namespace std;
//max min vecotr
//cin cout
using VI = vector<int>;
using PII = pair<int, int>;
using ll = long long;
int idx = 0;
int head[2010];
VI gar[510];
int p[510],t[510],s[510],g[510];
int med[510];//记录每个药水 对应的位置
int pos[510];//记录每个位置 对应的药水编号
ll dp[1<<11];
int fa[510];
int vis[1<<11][510];
int n;
int maxn = 0;
int tot = 0;
priority_queue , greater> pq[1 << 11];
 
void solve(){
 
    for(int i = 0 ; i < tot ; i++){
        queue<int> q;
        q.push(med[i]);
        while(q.size()){
            int u = q.front();
            q.pop();
            if(pos[u] != -1 && i != pos[u]) fa[pos[u]] = i;
            //当前的这个点是一瓶药水，并且不是初始的药水 ，那么就记录这瓶药的最近祖先捏
            else for(auto x : gar[u]) q.push(x);
        }
    }
 
 
}
 
 
int main(){
    memset(pos , -1 , sizeof pos);
    memset(med , -1 , sizeof med);
    memset(fa , -1 , sizeof fa);
    memset(dp , -1 , sizeof dp);
    cin>>n;
    for(int i = 2; i <= n; i++){
        cin>>p[i]>>t[i]>>s[i]>>g[i];
        if(t[i] == 2){
        	
            med[tot] = i;
            pos[i] = tot;
            tot++;
 
        }else{
            maxn = max(maxn , s[i]);
        }
        gar[p[i]].push_back(i);
   }
    ll now = 1 ;
    dp[0] = 1;
	vis[0][1] = 1;
    for(auto to : gar[1]){
        if(t[to] == 1) pq[0].push({s[to] , to});
    }
    while(pq[0].size()){
        auto x = pq[0].top().second;
        if(now < s[x]) break;
        now += g[x];
        vis[0][x] = 1;
        pq[0].pop();
        for(auto to : gar[x]){
            if(t[to] == 1) pq[0].push({s[to] , to});
        }
    }
	//11111
    dp[0] = now;
    solve();
    //cout<
   /* for(int i = 0 ; i < tot ; i++){
    	cout<
    }
    cout<
    for(int i = 0 ; i < (1 << tot) ; i++){
        if(dp[i] > maxn){
            cout<<"Yes\n";
            return 0;
        }
        if(dp[i] < 0) continue;
        //cout<
        //dp[i] = -1e9;
        for(int j = 0 ; j < tot ; j++){
            if(!vis[i][p[med[j]]]) continue;
            if((i >> j) & 1) continue;
            if(fa[j] != -1 && ((i >> fa[j]) & 1) == 0) continue;
            int ne = i | (1 << j);
            ll val = dp[i] * g[med[j]];
//            priority_queue , greater> z;
            auto z = pq[i];
            for(int k = 1 ; k <= n ; k++) vis[ne][k] = vis[i][k];
            vis[ne][med[j]] = 1;
            for(auto u : gar[med[j]]){
                if(t[u] == 1) z.push({s[u] , u});
            }
            while(z.size()){
                auto x = z.top().second;
                if(val < s[x]) break;
                val += g[x];
                vis[ne][x] = 1;
                z.pop();
                for(auto to : gar[x]){
                    if(t[to] == 1) z.push({s[to] , to});
                }
 
            }
            if(val > dp[ne]) dp[ne] = val , pq[ne] = z;
        }
 
 
 
    }
    cout<<"No\n";
 
}
 
 
 

只能说这个树上状压属实给我干崩溃

首先一定是尽量先打怪再吃药，于是就可以通过枚举药水的喝法 ， 解决问题

1.如果当前状态为 i   想喝第 j 瓶药水，那么这个药水j的 父节点是必须的走到的

2.当前这个的如果存在一个祖先为药水，那么祖先必定的被喝，

3.当前药水  j 不在 状态 i 中

然后考虑每次该怎么操作，对于状态 i - > ne

对于每个状态都开一个堆，堆里剩下的都是杀不掉的怪

dp的值一定是变大的，所以我们新建一个堆，继承 i 里面的所有值（状态 i 杀不掉的）

同时将  j 药水 可达的怪兽点也加入到堆中，

然后就开始从小到大，开始刷怪，遇到刷不动的怪就结束。

——————————————————————

建议下次设变量的时候把 id 和 pos 换个位置

id 记录当前位置的编号，pos 记录当前编号的位置