CodeForces - 191A Dynasty Puzzles(dp)

以你之姓@ 2022-06-07 03:15 95阅读 0赞

[点我看题][Link 1]

题意:就是有一些字符串作为名字,每个串前面的最后一个字母和当前串的前一个字母相同则可以连接起来,最终要求首尾字母相同的串的最大长度为多少.

分析:(eeeeem,作为dp方面的辣鸡,还是很不齿的写下了这边博客即使这题很简单

比赛的时候是记录每个串是否能够和前面某一个串进行拼接,显而易见这种想法完全不可取,然后,看了题解,额这个题确实比较简单,首先我们用dp\[i\]\[j\]表示字符串以i(i+'a')开始,以j(j+'a')结束的串的最大长度,那么dp\[i\]\[j\]的转移方程应该怎么写呢?我们先依次遍历每一个串,串的首字母为p,尾字母为q,依次遍历26个字母,先判断dp\[j\]\[p\]是否存在,存在的话,那么专用方程dp\[j\]\[q\]=max(dp\[j\]\[q\],dp\[j\]\[p\]+len);其中len为当前字符串的长度,最后做一个更新dp\[p\]\[q\]=max(dp\[p\]\[q\],len),处理完这些就要去找一个最终答案了,最终答案要满足首尾字母相同,所以也就是dp\[i\]\[i\]里面最大的那个.

参考代码:

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    const int maxn = 5e5+10;
    int n;
    char name[maxn][15];
    int dp[30][30];
    
    int main()
    {
        while( ~scanf("%d",&n))
        {
            mem(dp,0);
            for( int i = 0; i < n; i++)
                scanf("%s",name[i]);
    
            for( int i = 0; i < n; i++)
            {
                int len = strlen(name[i]);
                int p = name[i][0]-'a';
                int q = name[i][len-1]-'a';
                for( int j = 0; j < 26; j++)
                {
                    if( !dp[j][p])
                        continue;
                    dp[j][q] = max(dp[j][q],dp[j][p]+len);
                }
               dp[p][q]=max(dp[p][q],len);
            }
            int ans = 0;
            for( int i = 0; i < 26; i++)
                ans = max(ans,dp[i][i]);
            printf("%d\n",ans);
        }
    
        return 0;
    }

[Link 1]: http://codeforces.com/problemset/problem/191/A