Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*
- import java.util.*
- import java.util.stream.Stream
- import kotlin.collections.ArrayList
- import kotlin.collections.HashMap
- class FastIO(private val inp: InputStream, private val out: OutputStream) : PrintWriter(out, false)
- {
- private val reader = BufferedReader(InputStreamReader(inp))
- private var tokenizer = StringTokenizer("")
- fun get() : String?
- {
- while (!tokenizer.hasMoreTokens())
- {
- val s = reader.readLine() ?: return null
- tokenizer = StringTokenizer(s)
- }
- return tokenizer.nextToken()
- }
- fun getWord() : String = get()!!
- fun getInt() : Int = getWord().toInt()
- fun getLong() : Long = getWord().toLong()
- fun getDouble() : Double = getWord().toDouble()
- fun getLine() : String?
- {
- tokenizer = StringTokenizer("")
- return reader.readLine()
- }
- }
- fun main(args: Array<String>)
- {
- // FastIO(FileInputStream("paint.in"), FileOutputStream("paint.out")).use {
- // main(it)
- // }
- FastIO(System.`in`, System.out).use {
- main(it)
- }
- }
- fun colorToInt(s: String, i: Int) : Int
- {
- return s[i].toInt() - 'A'.toInt() + 1
- }
- fun main(io: FastIO)
- {
- io.getInt()
- val s = io.getLine()!!
- val n = s.length
- // Хранит время работы в часах
- val d = Array(n, {Array(n, {IntArray(40, {0})})})
- // Хранит значения k (для востановления ответа)
- val p = Array(n, {Array(n, {IntArray(40, {-1})})})
- for (i in 0 until n)
- {
- val fc = colorToInt(s, i)
- for (c in 0 until 40)
- {
- if (fc == c)
- d[i][i][c] = 0
- else
- d[i][i][c] = 1
- }
- }
- for (len in 2..n)
- {
- for (i in 0..n - len)
- {
- val j = i + len - 1
- val fc = colorToInt(s, i)
- for (c in 0 until 40)
- {
- // Если первый элемент уже покрашен в нужный цвет
- if (fc == c)
- {
- d[i][j][c] = d[i + 1][j][c]
- }
- else
- {
- d[i][j][c] = 99999999
- // Ищим наиболее оптимальную k
- for (k in i..j)
- {
- var nv = d[i + 1][k][fc] + 1
- if (k + 1 <= j) nv += d[k + 1][j][c]
- if (nv < d[i][j][c])
- {
- d[i][j][c] = nv
- p[i][j][c] = k
- }
- }
- }
- }
- }
- }
- io.println(d[0][n - 1][0])
- fun rec(i: Int, j: Int, c: Int)
- {
- if (i > j) return
- val k = p[i][j][c]
- if (k == -1) return
- io.print(i + 1)
- io.print(' ')
- io.print(k + 1)
- io.print(' ')
- io.println(s[i])
- if (i + 1 < n && s[i] != s[i + 1])
- rec(i + 1, k, colorToInt(s, i))
- rec(k + 1, j, c)
- }
- rec(0, n - 1, 0)
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement