nyist oj 37 回文字符串（动态规划经典）

回文字符串

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 4

即为回文字符串的就是一个正读反读都完全一致的字符串体例,例如"aba"之类的形式

请提供一个整数N（其中N满足条件：大于零且小于一百）
随后的N行
每行为一个字符串
每个字符串长度不得超过一千字

输出 每行输出所需添加的最少字符数

样例输入

样例输出

来源

IOI 2000

开始看到这道题的时候，一开始没有想到特别好的解决方法；由于题目涉及动态规划的内容也朝着这方面进行了思考。随后参考了他人的解题思路之后恍然大悟啊：可以通过将给定字符串反转处理后再与原字符串一起计算它们之间的最长公共子序列；接着通过用字符串长度减去最长公共子序列长度的方法得出所需添加的最少字符数量；到了这里这个题目就变得容易解决了；后面直接运用相关算法实现（LIC水过）的状态转移方程与之前遇到的问题基本一致；

  #include <cstdio>

    
 #include <cstring>
    
 #define max(a,b) a>b?a:b