この問題は、以下の DP を用いて解くことができます。

\(dp_i = \) 今までに部室にした部屋の集合が \(i\) の時の嬉しさの最大値

この DP の定義の下で遷移をする時に必要なものを考えると、今までに経過した日数 … ① と、次に部室にすることのできる部屋の集合 … ② だとわかります。

① … \(i\) の \(popcount\) (ビット列 の \(1\) が立っている個数) に一致します。

② … 各頂点ごとにどの頂点が隣接しているかを記録しておくことで、毎回今まで部室にした部屋についての隣接情報を見ると、\(O(N^2)\) で計算できます。この時、どの頂点が隣接しているかをビット列で持っておくと、今まで部室にした頂点について \(or\) を取れば良いので、\(O(N)\) でも計算できます。

よってこの問題が \(O(2^N \times N)\) で解けました。

DP テーブルを予め十分に小さな値で埋めるなどして、不正な順番で部屋を部室にすることがないようにすることも大切です。

回答例(C++)

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

int inf = 1001001001;
int dp[1 << 15];

int main() {
    int N,M;
    cin >> N >> M;
    vector<int>nxt(N);
    for(int i = 0; i < M; i++) {
        int U,V;
        cin >> U >> V;
        U--;
        V--;
        nxt[U] |= (1 << V);
        nxt[V] |= (1 << U);
    }
    vector<vector<int>>A(N,vector<int>(N));
    for(int i = 1; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }
    for(int i = 0; i < (1 << N); i++) {
        dp[i] = -inf;
    }
    dp[1] = 0;
    for(int i = 1; i < (1 << N); i++) {
        int day = __builtin_popcount(i);
        int tmp = 0;
        for(int j = 0; j < N; j++) {
            if(1 & (i >> j)) {
                tmp |= nxt[j];
            }
        }
        for(int j = 0; j < N; j++) {
            if((1 & (tmp >> j)) && !(1 & (i >> j))) {
                dp[i|(1 << j)] = max(dp[i|(1 << j)],dp[i]+A[day][j]);
            }
        }
    }
    cout << dp[(1 << N)-1] << endl;
}