[中山市赛 2023] 永别

Luogu
IDLGB4336
Time1000ms
Memory512MB
DifficultyP4
动态规划 DP2023广东区间 DP科创活动小学活动
你做了一个梦,梦里有一个字符串,这个字符串无论正着读还是倒着读都是一样的,例如:$\tt abcba$ 就符合这个条件。 但是你醒来时不记得梦中的字符串是什么,只记得它是另一个字符串 $S$ 的子序列,你想知道梦中字符串最长是多少。 提示:字符串 $A$ 是字符串 $B$ 的子序列当且仅当从 $B$ 中删除若干个字符(可以不删)后可以变成 $A$。例如:$\tt acd$ 是 $\tt achda$ 的子序列,因为从 $\tt achda$ 中删去第 $3$ 个和第 $5$ 个字符后就是 $\tt acd$。 ## Input 第一行一个正整数 $len$,表示字符串 $S$ 的长度。 第二行一个长度为 $len$ 的字符串,表示字符串 $S$。 ## Output 第一行包含一个整数,表示梦中字符串最长的长度。 [samples] ## Note ### 样例解释 从 $\tt acbdcaa$ 中删去第 $4$ 个和第 $7$ 个字符后变成 $\tt acbca$ 就满足正着读还是倒着读都是一样,不难发 现这是最长的。 ### 数据范围 对于 $15\%$ 的数据,$len \le 20$。 对于 $30\%$ 的数据,$len \le 200$。 对于 $45\%$ 的数据,$len \le 700$。 对于另外 $15\%$ 的数据,$len \le 800$,字符串中只会出现字母 $\tt a$ 和 $\tt b$。 对于 $100\%$ 的数据,$3 \le len \le 1000$,字符串中只会出现英文小写字母。
Samples
Input #1
7
acbdcaa
Output #1
5
API Response (JSON)
{
  "problem": {
    "name": "[中山市赛 2023] 永别",
    "description": {
      "content": "你做了一个梦,梦里有一个字符串,这个字符串无论正着读还是倒着读都是一样的,例如:$\\tt abcba$ 就符合这个条件。 但是你醒来时不记得梦中的字符串是什么,只记得它是另一个字符串 $S$ 的子序列,你想知道梦中字符串最长是多少。 提示:字符串 $A$ 是字符串 $B$ 的子序列当且仅当从 $B$ 中删除若干个字符(可以不删)后可以变成 $A$。例如:$\\tt acd$ 是 $\\tt ach",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4336"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你做了一个梦,梦里有一个字符串,这个字符串无论正着读还是倒着读都是一样的,例如:$\\tt abcba$ 就符合这个条件。\n\n但是你醒来时不记得梦中的字符串是什么,只记得它是另一个字符串 $S$ 的子序列,你想知道梦中字符串最长是多少。\n\n提示:字符串 $A$ 是字符串 $B$ 的子序列当且仅当从 $B$ 中删除若干个字符(可以不删)后可以变成 $A$。例如:$\\tt acd$ 是 $\\tt ach...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments