暑假集训单切赛第一场 CF 191A Dynasty Puzzles

题意不说了,看原题吧,思路见代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm> using namespace std;
int n;
char str[];
int len;
char a,b; //a为名字的开头字符,b为名字的结尾字符
long long dp[][]; //dp[i][j]记录以字母i开头和字母j结尾的朝代名长度 ,最后只要遍历一遍dp[i][i],取最大长度的即可
int main()
{
int tmp;
memset(dp,,sizeof(dp));
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%s",str);
len=strlen(str);
a=str[];
b=str[len-];
int flag=;
//如果以a结尾且不等于0的朝代名长度加上他的名字,比现有的朝代名更长,则更新。
for(int j=;j<=;j++){
tmp=a-'a';
if(dp[j][tmp]!= && dp[j][tmp]+len>dp[j][b-'a']){
flag=;
dp[j][b-'a']=dp[j][tmp]+len;
}
}
//如果他名字足够长,也可以直接当一个朝代的首位皇帝
if(dp[a-'a'][b-'a']<len)
dp[a-'a'][b-'a']=len;
}
long long ans=;
//遍历对角线上的,取最大值
for(int j=;j<=;j++){
if(dp[j][j]>ans)
ans=dp[j][j];
}
printf("%I64d\n",ans);
return ;
}
上一篇:Android broadcast


下一篇:暑假集训单切赛第一场 POJ 2309 BST(找规律的题)