本题题意：先给你说明有几个点，然后给你几个点的之间的距离，问将这些点分在两边，求点距离的最大值
dfs最怕的就是你的重复计算，一不小心把以前走过的路又走了一遍 例如本题卡我这么久的T,我因为是我剪的不够好，我考虑到两边重复的情况，所有A那边最少数量不能少于一半，不能其实AB边发生了重复 例如A1，2 B 3 这种情况等价于 A 3 B 1，2 但我没有写好的地方是，这题的思想是组合，也就是前面一步确定好状态后不能回头！！！ 而我却将它写成了组合，导致自己写出了A 1,2 B 3 然后有会再出现 A 2,1 B 3 的情况 其他没啥好注意的了，只要不要在传参的时候，传错就行啦 上代码： 1.两个数组
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; int a[25][25]; int A[25],B[25],maxn = 0,n; void DFS(int w,int nb ,int Vs,int na) { if( na <= n/2) return; for (int i = w; i <= n; i++)//转移 { int kk = Vs; if(A[i]!= 0 ) { for (int j = 1; j <= n; j++){ if( A[j]!= 0 ) kk+=a[A[i]][A[j]]; } for (int j = 1; j <= nb; j++){ kk-=a[A[i]][B[j]]; } if(kk > maxn) maxn = kk; if(kk > Vs){ B[nb+1] = A[i]; A[i] = 0; DFS(i+1,nb+1,kk,na-1);//这步的 i+1 !!!!!!! A[i] = B[nb+1]; B[nb+1] = 0; } } } } int main() { scanf("%d",&n); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) scanf("%d",&a[i][j]); } for (int i = 1; i <= n; i++) { A[i] = i; } DFS(1,0,0,n); cout<<maxn<<endl; }一维数组，其实保存到底这个数在左在右01判断即可
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; int a[25][25]; int A[25],maxn = 0,n; void DFS(int w, int Vs,int na) { //if( na <= n/2) return; for (int i = w; i <= n; i++)//转移 { A[i] = 0; int kk = Vs; for (int j = 1; j <= n; j++){ if( A[j]!= 0 ) kk+=a[i][j]; else kk-=a[i][j]; } if(kk > maxn) maxn = kk; if(kk > Vs){ DFS(i+1,kk,na-1); } A[i] = 1; } } int main() { scanf("%d",&n); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) scanf("%d",&a[i][j]); } for (int i = 1; i <= n; i++) A[i] = 1; DFS(1,0,n); cout<<maxn<<endl; }