提出詳細

提出id	提出時刻	ユーザー名	問題	言語	判定状況	判定	実行時間
115036	2023-10-26 06:41:50	momoyuu	H	cpp	19/19	AC	435

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

int main(){ 
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
       
    int n;
    cin>>n;
    vector<string> s(n);
    for(int i = 0;i<n;i++) cin>>s[i];
    vector<vector<bool>> dp(1<<n,vector<bool>(n,0));
    for(int i = 0;i<n;i++) dp[1<<i][i] = 1;
    for(int i = 0;i<1<<n;i++){
        for(int j = 0;j<n;j++){
            if(!dp[i][j]) continue;
            for(int k = 0;k<n;k++) if(~i>>k&1){
                if(s[j].back()==s[k][0]) dp[i|(1<<k)][k]  = 1;
            }
        }
    }
    int ans = 0;
    for(int i = 0;i<1<<n;i++){
        for(int j = 0;j<n;j++){
            if(!dp[i][j]) continue;
            int now = 0;
            for(int k = 0;k<n;k++) if(i>>k&1) now += s[k].size();
            ans = max(ans,now);
        }
    }
    cout<<ans<<endl;
}

sample1.txt AC 2
sample2.txt AC 2
sample3.txt AC 3
case1.txt AC 130
case2.txt AC 128
case3.txt AC 129
case4.txt AC 126
case5.txt AC 125
case6.txt AC 401
case7.txt AC 401
case8.txt AC 2
case9.txt AC 10
case10.txt AC 7
case11.txt AC 7
case12.txt AC 7
case13.txt AC 18
case14.txt AC 7
case15.txt AC 10
case16.txt AC 435
435 AC435 AC