题单链接

https://vjudge.net/article/2605

CodeForces-191A Dynasty Puzzles

Codeforces Round #121 (Div. 1)

题意

给出 n 个小写字母组成的字符串。

• 两个字符串如果前者的最后一个字母与后者的首字母相同，那么两者可以连接；
• 还要求最后得到的字符串的首尾字母也要相同；

求最长的满足要求的字符串的长度是多少。

思路

记 f[x][y] 为从第一个字符串到当前字符串，字母 x 到字母 y 的最长字符串的长度。
最后遍历f[x][x]，相加就是答案。

转自：https://dilthey.cnblogs.com/

然后问题是如何初始化:
其他数据肯定是负无穷
又因为我们所求的f[x][x]对答案的贡献最小为0，因此这些设为0.

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int dp[36][36];
string s;
signed main()
{
    int n;
    cin >> n;
    for (int i = 0; i < 30; i++)
        for (int j = 0; j < 30; j++)
            dp[i][j] = -0x3f3f3f3f;
    for (int i = 0; i < 30; i++)
        dp[i][i] = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        int be = s[0] - 'a';
        int en = s[s.length() - 1] - 'a';
        for (int i = 0; i < 26; i++)
        {
            if (dp[i][be] == -0x3f3f3f3f)
                continue;
            dp[i][en] = max(dp[i][en], dp[i][be] + (int)s.length());
        }
    }
    int ans = 0;
    for (int i = 0; i < 26; i++)
        ans = max(ans, dp[i][i]);
    cout << ans << endl;
    return 0;
}

CodeForces-455A Boredom

Codeforces Round #260 (Div. 1)

题意

思路

代码

CodeForces-1061C Multiplicity

Codeforces Round #523 (Div. 2)

题意

思路

代码

4 CodeForces-1110D
Jongmah
3102
Codeforces Global Round 1
5 CodeForces-1312E
Array Shrinking
4844
Educational Codeforces Round 83 (Rated for Div. 2)
6 CodeForces-245H
Queries for Number of Palindromes
4856
CROC-MBTU 2012, Elimination Round (ACM-ICPC)