CF191A Dynasty Puzzles

tangtangpeng · 2022-08-14 22:07:30 · 个人记录

题意

给你n个单词，要你选出若干个将它们依次拼接起来，要求每一个单词的最后一个字母与下一个单词的前一个字母相同（最后一个单词的最后一个字母与第一个单词的第一个字母相同，相当于形成一个环），最大化拼接起来的单词串总长

思路

答案的单词串首尾相等，那么我们以此为突破口设计状态，为了方便，将['a','z']映射到[0,25]上，f[l][r]表示以l开头，r结尾的单词串的最大长度，那么对于每一个长为len的单词s有

最后ans=\max\limits_{i=0}^{25}\{f[i][i]\}

代码

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

const int N = 30;
int n, f[N][N];
int ans;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        char s[N];
        scanf("%s", s);
        int len = strlen(s);
        //cout << len << endl;
        int l = s[0] - 'a', r = s[len - 1] - 'a';
        for(int j = 0; j < 26; j++)
            if(f[j][l]) f[j][r] = max(f[j][r], f[j][l] + len);
        f[l][r] = max(f[l][r], len);
    }
    for(int i = 0; i < 26; i++)
        ans = max(ans, f[i][i]);
    printf("%d", ans);
    return 0;
}