提出詳細

提出id	提出時刻	ユーザー名	問題	言語	判定状況	判定	実行時間
114790	2023-10-24 08:08:17	hiikunZ	H	cpp	19/19	AC	216

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const ll MAX = 1e18;
ll N;
vector<string> S(16);
vector<vector<ll>> DP(1 << 16,vector<ll>(16,-1));
ll solve(ll bit,ll lst){
    if(DP[bit][lst] != -1) return DP[bit][lst];
    ll ans = 0;
    for(ll i = 0;i < N;i++){
        if(bit & (1 << i)) continue;
        if(S[lst][S[lst].size() - 1] == S[i][0]){
            ans = max(ans,(ll)S[i].size() + solve(bit | (1 << i),i));
        }
    }
    return DP[bit][lst] = ans;
}
int main(){
    cin >> N;
    for(ll i = 0;i < N;i++) cin >> S[i];
    ll ans = 0;
    for(ll i = 0;i < N;i++){
        ans = max(ans,(ll)S[i].size() + solve(1 << i,i));
    }
    cout << ans << endl;
}

sample1.txt AC 18
sample2.txt AC 23
sample3.txt AC 25
case1.txt AC 21
case2.txt AC 30
case3.txt AC 41
case4.txt AC 26
case5.txt AC 27
case6.txt AC 216
case7.txt AC 196
case8.txt AC 18
case9.txt AC 24
case10.txt AC 26
case11.txt AC 29
case12.txt AC 33
case13.txt AC 21
case14.txt AC 24
case15.txt AC 26
case16.txt AC 205
216 AC216 AC