AcWing 324/poj 3345 Bribing FIPA(树形dp,分组背包)_windows

AcWing 324/poj 3345 Bribing FIPA(树形dp,分组背包)

传送门
这题的输入有点恶心,题目难度不是很大.
注意审题,题目说的是至少m个,而不是恰好m个.
状态设置很简单dp[i][j]表示i这颗子树选了至少j个的mincost.转移方程(y为i的子节点):
dp[i][j] = min{dp[u][j-k]+dp[y][k], 0<=k<=j, a[i]};
很简单的一个分组背包的模型.要注意的是选i这个节点更新应该在分组背包之后进行,不然的话背包的初始化是错误的.还有要处理的就是用一个虚节点0来把几颗树连在一起.
代码

#pragma GCC optimize(2)
#define LL long long
#define pq priority_queue
#define ULL unsigned long long
#define pb push_back
#define mem(a,x) memset(a,x,sizeof a)
#define pii pair<int,int>
#define fir(i,a,b) for(int i=a;i<=(int)b;++i)
#define afir(i,a,b) for(int i=(int)a;i>=b;--i)
#define ft first
#define vi vector<int>
#define sd second
#define ALL(a) a.begin(),a.end()
#define bug puts("-------")
#define mpr(a,b) make_pair(a,b)
#include <bits/stdc++.h>
#include <sstream>

using namespace std;
const int N = 1e3+10;

inline void read(int &a){
    int x = 0,f=1;char ch = getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    a = x*f;
}
int n,m,tot,w[N],nxt[N],head[N],to[N],dp[N][N],du[N],siz[N],ct=1;
string s[N];
map<string,int> mp;

void addedge(int x,int y){
    nxt[++ct] = head[x];head[x] = ct;to[ct] = y;
}

void pre(int u,int fa){
    siz[u] = 1;
    for(int i=head[u];i;i=nxt[i]){
        int y = to[i];
        if(y == fa) continue;
        pre(y,u);
        siz[u] += siz[y];
    }
}

void dfs(int u,int fa){
    dp[u][0] = 0;
    for(int i=head[u];i;i=nxt[i]){
        int y = to[i];
        if(y == fa) continue;
        dfs(y,u);
        afir(j,m,0){
            afir(k,m,0){
                int cur = j-k;
                if(cur < 0) continue;
                dp[u][j] = min(dp[u][j],dp[u][cur]+dp[y][k]);
            }            
        }
    }
    if(u){
        fir(i,0,siz[u]) dp[u][i] = min(dp[u][i],w[u]);
    }
}

void init(){
    mem(dp,0x3f);
    ct = 1;
    mem(head,0);
    mem(du,0);
    mem(siz,0);
    mp.clear();
    tot = 0;
}
int main(){
    while(cin >> n >> m){
        init();
        getline(cin,s[0]);
        fir(tt,1,n){
            getline(cin,s[++tot]);
            string name="";
            int idx = -1,cur = 0;
            while(s[tot][++idx]!=' ') name += s[tot][idx];
            while(isdigit(s[tot][++idx])) cur = cur*10+s[tot][idx]-'0';
            w[tot] = cur;
            mp[name] = tot;
        } 
        fir(i,1,tot){
            stringstream ss(s[i]);
            string str;
            int cur;
            ss >> str >> cur;
            while(ss >> str){
                addedge(i,mp[str]);
                addedge(mp[str],i);
                du[mp[str]]++;
            }
        }
        fir(i,1,tot){
            if(du[i]) continue;
            addedge(0,i);
            addedge(i,0);
        }
        pre(0,-1);dfs(0,-1);
        cout << dp[0][m] << endl;
    }
    
    return 0;
}    

/*
    dp[i][j] 表示i这个节点已经至少选了j个的mincost
*/