提出詳細

提出id	提出時刻	ユーザー名	問題	言語	判定状況	判定	実行時間
114892	2023-10-24 10:30:21	euommo	H	cpp	19/19	AC	194

#include <bits/stdc++.h>

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin.exceptions(std::cin.failbit);

  int N;
  std::cin >> N;

  std::vector<std::string> S(N);
  for (std::string &s: S)
    std::cin >> s;

  int ans = 0;
  std::vector<std::vector<int>> dp(1 << N, std::vector<int>(N, 0));
  for (int i = 0; i < (1 << N); ++i) {
    for (int j = 0; j < N; ++j) if (i >> j & 1) {
      for (int k = 0; k < N; ++k) if (k != j and (i >> k & 1) and S[k].back() == S[j][0])
        dp[i][j] = std::max(dp[i][j], dp[i ^ (1 << j)][k]);
      dp[i][j] += (int) S[j].size();
      ans = std::max(ans, dp[i][j]);
    }
  }

  std::cout << ans << '\n';

  return 0;
}

sample1.txt AC 2
sample2.txt AC 2
sample3.txt AC 3
case1.txt AC 155
case2.txt AC 131
case3.txt AC 133
case4.txt AC 133
case5.txt AC 127
case6.txt AC 166
case7.txt AC 165
case8.txt AC 2
case9.txt AC 7
case10.txt AC 5
case11.txt AC 4
case12.txt AC 7
case13.txt AC 10
case14.txt AC 3
case15.txt AC 7
case16.txt AC 194
194 AC194 AC