提出詳細

提出id	提出時刻	ユーザー名	問題	言語	判定状況	判定	実行時間
114878	2023-10-24 09:42:59	rk42745417	H	cpp	19/19	AC	403

#include <iostream>
#include <string>
#include <vector>

signed main() {
    int n;
    std::cin >> n;
    std::vector<std::string> arr(n);
    for (auto &a : arr)
        std::cin >> a;

    std::vector<std::vector<int>> edge(n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j && arr[i].back() == arr[j].front())
                edge[i].push_back(j);
    std::vector dp(1 << n, std::vector(n, 0));
    for (int i = 0; i < n; i++)
        dp[1 << i][i] = arr[i].size();
    for (int i = 0; i < (1 << n); i++)
        for (int j = 0; j < n; j++)
            for (int k : edge[j])
                if ((~i >> k & 1))
                    dp[i | (1 << k)][k] = std::max<int>(dp[i | (1 << k)][k], dp[i][j] + arr[k].size());
    int ans = 0;
    for (int i = 0; i < (1 << n); i++)
        for (int j = 0; j < n; j++)
            ans = std::max(ans, dp[i][j]);
    std::cout << ans << '\n';
}

sample1.txt AC 2
sample2.txt AC 2
sample3.txt AC 3
case1.txt AC 126
case2.txt AC 122
case3.txt AC 134
case4.txt AC 141
case5.txt AC 104
case6.txt AC 372
case7.txt AC 371
case8.txt AC 2
case9.txt AC 5
case10.txt AC 6
case11.txt AC 7
case12.txt AC 7
case13.txt AC 11
case14.txt AC 7
case15.txt AC 8
case16.txt AC 403
403 AC403 AC