秋祭 | 静岡高校工学部



卬高杯


提出詳細

提出id提出時刻ユーザー名問題言語判定状況判定実行時間
1148252023-10-24 08:36:53n_o_n_o_nHcpp19/19AC261

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

int N,dp[1<<16][52];
string S[16];


int main(){
    cin>>N;
    for(int i=0; i<N; i++)cin>>S[i];
    for(int i=0; i<(1<<N); i++)for(int j=0; j<52; j++)
    {
        for(int k=0; k<N; k++)if(i&(1<<k))
        {
            if(j<26)
            {
                if(S[k][0]==('a'+j)){
                    int c;
                    if('a'<=S[k].back()&&S[k].back()<='z')c=S[k].back()-'a';
                    else c=S[k].back()-'A'+26;
                    dp[i][j]=max(dp[i][j],dp[i-(1<<k)][c]+(int)S[k].size());
                }
            }
            else
            {
                if(S[k][0]==('A'+(j-26))){
                    int c;
                    if('a'<=S[k].back()&&S[k].back()<='z')c=S[k].back()-'a';
                    else c=S[k].back()-'A'+26;
                    dp[i][j]=max(dp[i][j],dp[i-(1<<k)][c]+(int)S[k].size());
                }
            }
        }
    }
    int ans=0;
    for(int i=0; i<N; i++)
    {
        int c;
        if('a'<=S[i][0]&&S[i][0]<='z')c=S[i][0]-'a';
        else c=S[i][0]-'A'+26;
        ans=max(ans,dp[(1<<N)-1][c]);
    }
    cout << ans << endl;
}

sample1.txt AC 2
sample2.txt AC 2
sample3.txt AC 3
case1.txt AC 261
case2.txt AC 238
case3.txt AC 232
case4.txt AC 228
case5.txt AC 233
case6.txt AC 225
case7.txt AC 218
case8.txt AC 2
case9.txt AC 17
case10.txt AC 13
case11.txt AC 5
case12.txt AC 7
case13.txt AC 28
case14.txt AC 7
case15.txt AC 13
case16.txt AC 254
261 AC261 AC