考虑将整个过程倒过来，那么每次就是消除距离最远的点对中的一个点。
我们就爆搜消除哪个点，把点状压起来，用map加个记忆化。

很诡异的是，我一开始只对所有’#‘状压，结果极限数据根本跑不过去，后来改成对所有点状压就突然跑得飞快，什么鬼啊，点多了不应该更慢了？？而且这两种方法在所有点都是’#'的情况下应该是一模一样的啊。。。

#include <bits/stdc++.h> #define ull unsigned long long using namespace std; const int N=71; int n=8; int x[N],y[N],m; int d[N][N]; map<ull,int> mp; template<class T> void checkmin(T &a,const T &b) { if (b<a) a=b; } template<class T> void checkmax(T &a,const T &b) { if (b>a) a=b; } class EllysChessboard { public: int minCost( vector <string> board ) ; }; int dfs(ull o,int K){ if (K<=1) return 0; if (mp[o]>=1) return mp[o]; int mx=0,q=-1,w=-1; for(int i=0;i<64;i++) if (o&(1ull<<i)) for(int j=i+1;j<64;j++) if ((o&(1ull<<j))&&d[i][j]>mx){ mx=d[i][j]; q=i;w=j; } mp[o]=min(dfs(o^(1ull<<q),K-1),dfs(o^(1ull<<w),K-1))+mx; return mp[o]; } int EllysChessboard::minCost(vector <string> a) { ull s=0; for(int i=0;i<n;i++) for(int j=0;j<n;j++) if (a[i][j]=='#'){ x[m]=i;y[m]=j; m++; s|=1ull<<(i*8+j); } //cout<<m<<endl; for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++) for(int l=0;l<n;l++) d[i*8+j][k*8+l]=abs(i-k)+abs(j-l); return dfs(s,m); }

附上T飞了的代码︿(￣——￣)︿
灰常正确有木有/(ㄒoㄒ)/~~+

#include <bits/stdc++.h> #define ull unsigned long long using namespace std; const int N=71; int n=8; int x[N],y[N],m; int d[N][N]; map<ull,int> mp; template<class T> void checkmin(T &a,const T &b) { if (b<a) a=b; } template<class T> void checkmax(T &a,const T &b) { if (b>a) a=b; } class EllysChessboard { public: int minCost( vector <string> board ) ; }; inline int dis(int q,int w){ return abs(x[q]-x[w])+abs(y[q]-y[w]); } int dfs(ull o,int K){ if (K==0||K==1) return 0; if (mp[o]>=1) return mp[o]; int mx=0,q=-1,w=-1; for(int i=0;i<m;i++) if (o&(1ull<<i)) for(int j=i+1;j<m;j++) if ((o&(1ull<<j))&&d[i][j]>mx){ mx=d[i][j]; q=i;w=j; } mp[o]=min(dfs(o^(1ull<<q),K-1),dfs(o^(1ull<<w),K-1))+mx; return mp[o]; } int EllysChessboard::minCost(vector <string> a) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) if (a[i][j]=='#'){ x[m]=i;y[m]=j; m++; } cout<<m<<endl; for(int i=0;i<m;i++) for(int j=0;j<m;j++) d[i][j]=dis(i,j); return dfs((1ull<<m)-1,m); }