题目链接：https://www.vijos.org/p/1048
很多人一看就想出了思路，不就是一个裸的dfs蛮。。。但是。。在n<=50的情况下，朴素会直接tle。。。。。
然后我就开始剪枝，剪了很多地方，然后多过了一个点。。。。。然后我就发现我的剪枝和我的dfs打的不行
然后我们先看看朴素的打法（打法多，我是一种非常原始的朴素算法）
bool check(int x,int dep){
for(int i=;i<=dep;i++)
if(map[a[i]][x]==)return ;
return ;
}
void dfs(int dep,int pos){
if(dep==m+){ans=max(ans,s);return;}
if(s+tot[n]-tot[pos-]<=ans)return;
for(int i=;i<=n,dep-+n-i+>=m;i++){
if(vis[i]==&&check(e[i].ord,dep-)){
vis[i]=;
a[dep]=e[i].ord;
s+=val[i];
dfs(dep+,i+);
s-=val[i];
a[dep]=;
vis[i]=;
}
}
return ;
}然后我的这个dfs本身就不够优化。。我其实可以换成不扩展深度dep，而是扩展当前的指针pos，代替我原来程序的i
另一个优化的地方，在这个朴素的程序里面也有，就是维护一个前缀和，如果当前值的大小+后面未遍历的所有值<=我们当前的ans，就跳过
然后就是对于是不是有矛盾的判断，我的朴素算法是邻接矩阵来暴力跑个O(n)来判断
这个位置可以优化，我们开一个二维数组en[i][j]，其中i代表初始序号为i的数，en[i][0]存这个i多少有矛盾的人，然后j就是第几个矛盾的人,e[i][j]就是和i有矛盾的第j个人的序号
然后在判断时加一个enm[x]数组，如果enm[x]==0，说明当前x是没有敌人的，然后就把x 的所有敌人的enm[i]++，标记这些人就有敌人了。。。
然后还剩一个优化的地方，就是排序，这个排序的主要作用是配合我们维护前缀和的剪枝，不过排序要注意排序后的序号和输入矛盾两人的序号可能不同，输入矛盾序号是按照最开始的序号来的，所以要稍微处理一下这个细节
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define maxn 60
using namespace std; int n,m,ans,s,sum,val[maxn],a[maxn],vis[maxn];
int tot[maxn],en[maxn][maxn],enm[maxn];
struct node{
int v,ord;
}e[maxn]; int comp(const void*a,const void*b){
return (*(struct node*)a).v<(*(struct node*)b).v?:-;
} void dfs(int pos){
if(pos==n+){ans=max(ans,s);return;}
if(s+tot[n]-tot[pos-]<=ans)return;
int o=e[pos].ord;
if(enm[o]==){
for(int i=;i<=en[o][];i++)
enm[en[o][i]]++;
s+=e[pos].v;
dfs(pos+);
s-=e[pos].v;
for(int i=;i<=en[o][];i++)
enm[en[o][i]]--;
}
dfs(pos+);
} int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&val[i]);e[i].v=val[i];e[i].ord=i;
}
e[].v=0x3f3f3f;
qsort(e,n+,sizeof(e[]),comp);
for(int i=;i<=n;i++){
tot[i]=tot[i-]+e[i].v;
}
int x,y;
while(scanf("%d%d",&x,&y)!=EOF){
en[x][++en[x][]]=y;
en[y][++en[y][]]=x;
}
dfs();
printf("%d",ans);
}
【总结】
DFS的优化着手点：
1.数据排序，加上对未来最大情况判断（本题表现为前缀和）
2.DFS的参数不用dep（选了几个数），而用pos（正在判断第几个数）
3.记录与自己有关系的人，不用邻接矩阵，用list[i][j]表示，list[i][0]为和自己有关系的人的个数