Advertisement
Guest User

Untitled

a guest
Jul 10th, 2018
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Kotlin 3.21 KB | None | 0 0
  1. import java.io.*
  2. import java.util.*
  3. import java.util.stream.Stream
  4. import kotlin.collections.ArrayList
  5. import kotlin.collections.HashMap
  6.  
  7. class FastIO(private val inp: InputStream, private val out: OutputStream) : PrintWriter(out, false)
  8. {
  9.     private val reader = BufferedReader(InputStreamReader(inp))
  10.     private var tokenizer = StringTokenizer("")
  11.  
  12.     fun get() : String?
  13.     {
  14.         while (!tokenizer.hasMoreTokens())
  15.         {
  16.             val s = reader.readLine() ?: return null
  17.             tokenizer = StringTokenizer(s)
  18.         }
  19.  
  20.         return tokenizer.nextToken()
  21.     }
  22.  
  23.     fun getWord() : String = get()!!
  24.     fun getInt() : Int = getWord().toInt()
  25.     fun getLong() : Long = getWord().toLong()
  26.     fun getDouble() : Double = getWord().toDouble()
  27.  
  28.     fun getLine() : String?
  29.     {
  30.         tokenizer = StringTokenizer("")
  31.         return reader.readLine()
  32.     }
  33. }
  34.  
  35. fun main(args: Array<String>)
  36. {
  37. //    FastIO(FileInputStream("paint.in"), FileOutputStream("paint.out")).use {
  38. //        main(it)
  39. //    }
  40.  
  41.     FastIO(System.`in`, System.out).use {
  42.         main(it)
  43.     }
  44. }
  45.  
  46. fun colorToInt(s: String, i: Int) : Int
  47. {
  48.     return s[i].toInt() - 'A'.toInt() + 1
  49. }
  50.  
  51. fun main(io: FastIO)
  52. {
  53.     io.getInt()
  54.     val s = io.getLine()!!
  55.     val n = s.length
  56.  
  57.     // Хранит время работы в часах
  58.     val d = Array(n, {Array(n, {IntArray(40, {0})})})
  59.  
  60.     // Хранит значения k (для востановления ответа)
  61.     val p = Array(n, {Array(n, {IntArray(40, {-1})})})
  62.  
  63.     for (i in 0 until n)
  64.     {
  65.         val fc = colorToInt(s, i)
  66.  
  67.         for (c in 0 until 40)
  68.         {
  69.             if (fc == c)
  70.                 d[i][i][c] = 0
  71.             else
  72.                 d[i][i][c] = 1
  73.         }
  74.     }
  75.  
  76.     for (len in 2..n)
  77.     {
  78.         for (i in 0..n - len)
  79.         {
  80.             val j = i + len - 1
  81.             val fc = colorToInt(s, i)
  82.  
  83.             for (c in 0 until 40)
  84.             {
  85.                 // Если первый элемент уже покрашен в нужный цвет
  86.                 if (fc == c)
  87.                 {
  88.                     d[i][j][c] = d[i + 1][j][c]
  89.                 }
  90.                 else
  91.                 {
  92.                     d[i][j][c] = 99999999
  93.  
  94.                     // Ищим наиболее оптимальную k
  95.                     for (k in i..j)
  96.                     {
  97.                         var nv = d[i + 1][k][fc] + 1
  98.                         if (k + 1 <= j) nv += d[k + 1][j][c]
  99.  
  100.                         if (nv < d[i][j][c])
  101.                         {
  102.                             d[i][j][c] = nv
  103.                             p[i][j][c] = k
  104.                         }
  105.                     }
  106.                 }
  107.             }
  108.         }
  109.     }
  110.  
  111.     io.println(d[0][n - 1][0])
  112.  
  113.     fun rec(i: Int, j: Int, c: Int)
  114.     {
  115.         if (i > j) return
  116.  
  117.         val k = p[i][j][c]
  118.  
  119.         if (k == -1) return
  120.  
  121.         io.print(i + 1)
  122.         io.print(' ')
  123.         io.print(k + 1)
  124.         io.print(' ')
  125.         io.println(s[i])
  126.  
  127.         if (i + 1 < n && s[i] != s[i + 1])
  128.             rec(i + 1, k, colorToInt(s, i))
  129.  
  130.         rec(k + 1, j, c)
  131.     }
  132.  
  133.     rec(0, n - 1, 0)
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement