logo AlgoBeat OnlineJudge
登录 注册

#104163. [BZOJ 4163] 字符串合成

内存限制：256 MiB 时间限制：5000 ms 标准输入输出
题目类型：传统 评测方式：文本比较
上传者： 匿名
提交 提交记录 统计 测试数据 讨论 题解

题目描述

给定四种对字符串 的操作：

  1. push_back(P)：在 后连接一个字符串 ，即 ，代价为 ；

  2. push_front(P)：在 前连接一个字符串 ，即 ，代价为 ；

  3. symmetry_back()：将 翻转后连接在 之后，即 ，代价为 ；

  4. symmetry_front()：将 翻转后连接在 之前，即 ，代价为 ；

给定一个目标串 ，要求你通过上述四种操作，用最少的代价合成出目标串，初始只有一个空串。

输入格式

第一行一个正整数 ，表示数据组数。

接下来 行，每组数据一行，为字符串 。

输出格式

每组数据一行输出一个正整数表示最少的代价。

样例

样例输入 #1

7 
c
aaaab
bbaaaacc
ababa
abba
baab
aaabacdbbdcabaaaaaaaaaaaab

样例输出 #1

1 
4 
7 
5 
3 
3
18

样例解释

{} -> c，代价为 ；

{} -> aa -> aaaa -> aaaab，代价为 ；

{} -> aa -> aaaa -> aaaacc -> bbaaaac，代价为 ；

{} -> ababa，代价为 ；

{} -> ab -> abba，代价为 ；

{} -> ab -> baab，代价为 ；

{} -> aaa -> aaaaaa -> baaaaaa -> baaaaaaaaaaaab -> aaabacdbbdcabaaaaaaaaaaaab， 代价为 。

数据范围与提示

对于 的数据，，。

显示分类标签

编辑器加载中 …
Powered by SYZOJ. Modified by Zemu (UnratedCheater).
项目源码 · 陶片放逐 · 新ICP备2026003452号-2
当前版本：V1.7.2-premium