ネックレスの並べ方を全通り調べて、美しさの最大値を計算することができますが、\(N=K=16\) の時並べ方は \(\frac{15!}{2}\) 通りあるため実行時間制限にひっかかってしまいます。

ここで巡回セールスマン問題と同じ要領でビットマスク動的計画法を行うことを考えます。

今回の問題を定式化すると。\(N\) 頂点で各頂点の重みが \(P_i\) で辺 \((i,j)\) の重みが \(C_{i,j}\) であるような完全グラフから 長さ \(K\) の閉路のうち、辺重みと点重みの合計の最大値を求める問題です。

まず、閉路をどう集合で表現するかを考えます。閉路はずらしてもおなじです。集合の一番小さい値を起点として固定します。

ここで\(\text{dp}\) を以下のように定義します。

\[ \text{dp}[S][v]=\text{Sに含まれるネックレスを全てつなげて起点から始めてネックレス} v \text{で終わるパスの辺重みの合計の最大値} \]

遷移は \(S\) に含まれない頂点 \(u\) について、

\(\text{dp}[S \cup \{u\}][u]\leftarrow \max(\text{dp}[S \cup \{u\}][u],\max_{v \in S} dp[S][v]+C_{v,u})\)

となります。

最後に、各状態から求めるべき実際の美しさは \(|S|=K\) となるような \(S\) および \(v \in S\) について \(\text{dp}[S][v]+C_{v,start}+\sum_{u \in S}P_u\) である。ここで \(start\) は \(S\) のの元の最小値である。

これらの最大値を求めればよいです。

以上で時間計算量 \(\mathrm{O}(2^N N^2)\) で解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (auto& e : p) cin >> e;
    vector<vector<int>> c(n, vector<int>(n, 0));
    for (auto& v : c)
        for (auto& e : v) cin >> e;
    vector<vector<int>> dp(1 << n, vector<int>(n, -1e9));
    for (int i = 0; i < n; ++i) dp[1 << i][i] = 0;
    for (int bit = 1; bit < (1 << n); ++bit) {
        int st = -1;
        for (int i = 0; i < n; ++i)
            if ((bit >> i) & 1) {
                st = i;
                break;
            }
        for (int i = 0; i < n; ++i) {
            if (!((bit >> i) & 1)) continue;
            for (int j = st + 1; j < n; ++j) {
                if ((bit >> j) & 1) continue;
                dp[bit | (1 << j)][j] = max(dp[bit | (1 << j)][j], dp[bit][i] + c[i][j]);
            }
        }
    }
    int ans = -1e9;
    for (int bit = 0; bit < (1 << n); ++bit) {
        if (popcount((unsigned)bit) != k) continue;
        int st = -1;
        int sump = 0;
        for (int i = 0; i < n; ++i)
            if ((bit >> i) & 1) {
                st = i;
                break;
            }
        for (int i = 0; i < n; ++i)
            if ((bit >> i) & 1) sump += p[i];
        for (int i = st; i < n; ++i) {
            if ((bit >> i) & 1) ans = max(ans, dp[bit][i] + c[st][i] + sump);
        }
    }
    cout << ans << endl;
}