题解 P5034 【果冻】

· · 题解

解法1：
我有信仰，我是MC玩家，输出0，预计得分3.

解法2：
我会暴力dfs，预计得分33分。

解法3：
我会特判，观察到k的取值范围以及树退化的情况，考虑特判，预计得分60-70分。

解法4：
我会模拟退火，出题人特意开了乐多赛制，期望得分0-100

解法5：
我会状压DP。我们可以记录每个节点的儿子。因为在变动节点的时候，他的儿子始终是不变的。
对于每一个集合S，记S'除去当前考虑的节点x,然后看他里面有几个点的儿子是x,然后减去这个距离再计算（转移）就可以了。时间复杂度O(n^2*2^n)，可以过全部的点。

代码：（100pts） 

#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,k,d[101],top,far;
int o[51][51],f[1<<20];
int son[1<<20];
string s,t;
map<string,int> qwq;
int num(int x){
    if(x==0)    return 0;
    return num(x-(x&-x))+1;
}
void dfs(int node){
    if(d[node]>1)
        far|=(1<<node-1);
    for(int i=1;i<=n;i++)
        if(o[node][i]){
            d[i]=d[node]+1;
            dfs(i);         
            son[node]|=(1<<i-1);
            son[node]|=son[i];
        }
    return ;
}
int main(){
    int cnt=1;
    cin>>n>>k;
    cin>>s; qwq[s]=1;
    for(int i=2;i<=n;i++){
        cin>>s>>t;
        qwq[s]=++cnt;
        o[qwq[t]][qwq[s]]=1;
    }
    dfs(1);
    for(int s=1;s<(1<<n);s++){
        for(int i=1;i<=n;i++){
            if(s&(1<<i-1)){
                int s1=s-(1<<i-1),dis=d[i];
                for(int j=1;j<=n;j++)
                    if(s1&(1<<j-1)&&(son[j]&(1<<i-1))&&d[j]>1)
                        dis--;
                if(dis<=1)  f[s]=max(f[s],f[s1]);
                else    f[s]=max(f[s],f[s1]+((num(s&far)+dis)&k));
            }
        }
    }
    cout<<f[(1<<n)-1]<<endl;
    return 0;
}

其实也不是很长，对吧