因为 \(n\) 很小，所以考虑状压 dp。
令 \(sta\) 为一个二进制整数，表示当前第 \(i\) 个点有没有被匹配。
那么显然对于每一个 \(sta\) 第 \(i,j\) 两点未被匹配的都可以用边 \((i,j)\) 来转移到 \(sta|(1<<i)|(1<<j)\)。
时间复杂度 \(O(2^n \times \frac{n(n-1)}{2})\)，极限数据中 \(\frac{n(n-1)}{2}=120\)，因此可以通过本题。
#include <cstdio>
#include <algorithm>
typedef long long ll;
const int N=(1<<16)-1;
int n;
int d[17][17];
ll dp[N+5],ans;
int main() {
scanf("%d",&n);
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) scanf("%d",&d[i][j]);
}
for(int sta=0;sta<=(1<<n)-1;sta++) {//枚举状态
for(int i=0;i<n;i++) {
if((sta>>i)&1) continue;//判断合法性
for(int j=i+1;j<n;j++) {
if((sta>>j)&1) continue;//判断合法性
dp[sta|(1<<i)|(1<<j)]=std::max(dp[sta|(1<<i)|(1<<j)],dp[sta]+d[i][j]);//转移
ans=std::max(ans,dp[sta|(1<<i)|(1<<j)]);
}
}
}
printf("%lld\n",ans);
return 0;
}