自动搬运

查看原文

来自洛谷，原作者为

	南城忆潇湘 今天又是摸鱼的一天

搬运于2025-08-24 22:06:24，当前版本为作者最后更新于2018-11-14 07:00:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解法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;
}

其实也不是很长，对吧