入力例の形だと扱いにくいので、辺を張り、辺の重みを行く先の文字数とします。
次にbitDPを行います。
すべての文字列が最初の文字列になる可能性があるので、あらかじめ0列目をそれぞれの文字数で初期化しておきます。遷移は次の位置をto、toの文字数をcostとしたとき
dp[i+(1<<to)][to] = max(dp[i+(1<<to)][to],dp[i][j]+cost);
で行うことができます。
計算量は`O(2^N N^2)`で十分高速です。

---

解答例(C++)

#include<bits/stdc++.h>
using namespace std;
int inf = INT_MAX/2;

int main(){
  int n; cin >> n;
  vector<pair<pair<char,char>,int>> vec(n);
  int memo;
  for(int i=0;i<n;i++){
    string s; cin >> s;
    int siz = s.size();
    if(i==0) memo=siz;
    vec[i] = {{s[0],s[siz-1]},siz};
  }
  vector<vector<pair<int,int>>> g(n);
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(i==j) continue;
      if(vec[i].first.second==vec[j].first.first){
        g[i].push_back({j,vec[j].second});
      }
    }
  }
  vector<vector<int>> dp((1<<n),vector<int>(n,-inf));
  for(int i=0;i<n;i++){
    dp[(1<<i)][i]=vec[i].second;
  }
  for(int i=0;i<(1<<n);i++){
    for(int j=0;j<n;j++){
      if(dp[i][j]<0) continue;
      for(auto p:g[j]){
        if(i>>p.first&1) continue;
        dp[i+(1<<p.first)][p.first] = max(dp[i+(1<<p.first)][p.first],dp[i][j]+p.second);
      }
    }
  }
  int ans = 0;
  for(int i=0;i<(1<<n);i++){
    for(int j=0;j<n;j++){
      ans = max(ans,dp[i][j]);
    }
  }
  cout << ans << endl;
}

---

コメント

要はしりとりです。