この問題は、bit DP によって解くことができます。

状態の定義

\(\mathrm{dp}[b]\) を、

• \(b\) のうち立っているビットを \(i_1,i_2,\ldots,i_k\) としたとき、頂点 \(i_1,i_2,\ldots,i_k\) についてはその頂点を端点とする辺を選んでいる、またはその頂点を端点とする辺は選ばないことを決定した際の、選んだ辺の重みの総和の最大値

と定義します。求めたいのは、 \(\mathrm{dp}[2^N-1]\) です。

遷移方法

\(\mathrm{dp}[b]\) を、\(b\) の昇順に求めていきます。ある状態からの遷移は、次に追加する辺の候補を全て試し、その辺の端点二つが \(b\) に含まれない場合追加すればよいです。 なお、\(b\) に含まれない最小の番号の頂点に着目することでより良い計算量で解くこともできます。実装例は後者になっています。

• 実装例(C++)

#include <bits/stdc++.h>
using namespace std;

#define rep(i, x) for(int i = 0; i < (x); i++)

int main() {
	int n;
	cin >> n;
	vector d(n, vector(n, 0));
	rep(i, n) {
		for(int j = i + 1; j < n; j++) cin >> d[i][j];
	}
	vector dp(1 << n, 0ll);
	rep(b, (1 << n) - 1) {
		int l = -1;
		rep(i, n) if(!(b >> i & 1)) {
			l = i;
			break;
		}
		rep(i, n) if(!(b >> i & 1)) {
			int nb = b | (1 << l) | (1 << i);
			dp[nb] = max(dp[nb], dp[b] + d[l][i]);
		}
	}
	cout << dp.back() << endl;
}

余談

この問題は多項式時間で解くこともできますが、アルゴリズムや実装の複雑さから、AtCoder の Rated で要求されることは基本的にないと考えられます。ジャッジは Library Checker にあるので、興味のある方は調べてみてください。