package main import . "fmt" import . "os" import bf "bufio" import . "slices" func main() { rd:=bf.NewReader(Stdin) var n int Fscan(rd,&n) ss := make([]string, 0, n) for i := 0; i < n; i++ { var s string Fscan(rd,&s) if !IsSorted([]byte(s)) { continue } ss = append(ss, s) } SortStableFunc(ss, func(a, b string) int { d := int(a[len(a)-1])-int(b[len(b)-1]) if d == 0 { return int(a[0])-int(b[0]) } else { return d } }) dp := make([]int, 'z'-'a'+1) for _, s := range ss { w := len(s) x := int(s[0])-'a' y := int(s[w-1])-'a' dp[y] = max(dp[y],Max(dp[:x+1])+w,w) } Println(Max(dp)) } /* 考察 まず入力のうち良い文字列のみをピックアップ 各文字列の末尾文字昇順に並べる(が良いと思う…?) 動的計画法 DP[連結した文字列の末尾文字] = 最大の長さ として DP[Si[-1]] = MAX(DP[Si[-1]], MAX(DP['A':Si[0]])+LEN(Si), LEN(Si)) で更新 答えはMAX(DP['A':'Z']) 実行時間が間に合うかわからん TLEするかも? TLEしたら間に合う方法を考える */