#PQJ1553x1210. QOJ 1553_1210

    ID: 2660 传统题 4000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2021 集训字符串贪心

QOJ 1553_1210

Japanese Olympiad in Informatics 2014/2015 Spring Training Camp/Qualifying Trial March 19–25, 2015, Komaba/Yoyogi, Tokyo Contest Day 3 – AAQQZ AAQQZ (AAQQZ) 2015 年の国際情報オリンピックはカザフスタンで行われる.カザフスタンの「カザフ」は,アルファベッ トで“QAZAQ” と綴られることがある.このQAZAQ は回文である.このことを知ったJOI 君は,回文が 好きになって,目についた文字列から回文を作ることにした. JOI 君が見つけたのは長さがN の文字列である.各文字には1 からC までの整数が定まっており,文字列の 文字を整数に置き換えた数列をS = (S 1, S 2, . . . , S N) とする.この数列のi 番目からj 番目まで(1 ≦i ≦j ≦N) を取り出した数列(S i, S i+1, . . . , S j) を断片(i, j) と呼ぶ.断片(i, j) がそれを逆転させた数列と等しいとき, すなわち,(S i, S i+1, . . . , S j) = (S j, S j−1, . . . , S i) が成り立つとき,断片(i, j) は回文である. JOI 君は以下の操作により回文を作る.

  1. まず,S の断片を1 つ選ぶ.選んだ断片をT とおく.
  2. 断片T を昇順にソートしたものをT ′ とおく.
  3. 数列S に対し,断片T をT ′ に置き換える.置き換えたものをS ′ とする.すなわち,JOI 君が断片 j として,S ′ = (i, j) を選んだとき,S i, S i+1, . . . , S j を昇順にソートしたものをT ′ i ≦T ′ i+1 ≦. . . ≦T ′ (S 1, S 2, . . . , S i−1, T ′ i , T ′ i+1, . . . , T ′ j, S j+1, . . . , S N) とする.
  4. その後,S ′ の断片で回文になっているものを探す. JOI 君はこの操作により,できるだけ長い回文を作りたい. 課題 JOI 君の見つけた文字列を表す数列S が与えられる.JOI 君が作ることができる回文の長さの最大値を求 めよ. 入力 標準入力から以下の入力を読み込め. • 1 行目には,整数N,C が空白を区切りとして書かれている.N はJOI 君の見つけた文字列の長さを表 す.C は文字に定められた整数の上限を表す. • 続くN 行には,JOI 君の見つけた文字列を表す数列S の情報が書かれている.これらの行のうちのi 行目(1 ≦i ≦N) には整数S i が書かれている.S i は数列S のi 番目の整数を表す. 出力 標準出力に,JOI 君が作ることができる回文の長さの最大値を表す整数を1 行で出力せよ. AAQQZ– 1 / 3 Japanese Olympiad in Informatics 2014/2015 Spring Training Camp/Qualifying Trial March 19–25, 2015, Komaba/Yoyogi, Tokyo Contest Day 3 – AAQQZ 制限 すべての入力データは以下の条件を満たす. • 1 ≦N ≦3 000. • 1 ≦C ≦3 000. • 1 ≦S i ≦C (1 ≦i ≦N). 小課題 小課題1 [10 点] 以下の条件を満たす. • N ≦50. • C ≦50. 小課題2 [90 点] 追加の制限はない. 入出力例 入力例1 出力例1 12 26 8 26 17 17 17 1 26 1 17 19 20 1 14 AAQQZ– 2 / 3 Japanese Olympiad in Informatics 2014/2015 Spring Training Camp/Qualifying Trial March 19–25, 2015, Komaba/Yoyogi, Tokyo Contest Day 3 – AAQQZ この入力例では,N = 12,C = 26 で,S = (26, 17, 17, 17, 1, 26, 1, 17, 19, 20, 1, 14) である.ここで,断片 (4, 8) を昇順にソートすることでS ′ = (26, 17, 17, 1, 1, 17, 17, 26, 19, 20, 1, 14) となり,断片(1, 8) が回文にな る.この回文の長さは8 であり,これが最長である. 入力例2 出力例2 4 3 3 1 2 3 2 この入力例では,S = (1, 2, 3, 2) である.ここで,断片(1, 1) を昇順にソートすることで,S ′ = (1, 2, 3, 2) となる.S とS ′ は同じ数列である.S ′ の断片(2, 4) が回文になる.この回文の長さは3 であり,これが最 長である. AAQQZ– 3 / 3