ZOJ 2609. Crazy Painter

Brief description:

.矩形染色问题。要给 m×n 的矩阵上色,每个格子要求的颜色给定,有三种染色操作:

  1. 给连续一段水平格子染成某种颜色,花费为 h
  2. 给连续一段水平格子染成某种颜色,花费为 v
  3. 给一个单独格子染成某种颜色,花费为 s

要求花费最小的上色方案,注意不能给同一个格子先后染两种不同颜色。

ゆっくり読んでください ...

ZOJ 2112. Dynamic Rankings

Brief description:

给定一个长度为 N 的已知序列 A[i] (1≤i≤N),要求动态维护 M 次以下操作:
1、Q a b k 查询 A[a], A[a+1], A[a+2], …, A[b] (1≤a≤b≤N) 中,第 k 小的数。(Start From 1 ...
2、C x y 修改 A[x] 的值为 y。
( .. N ≤ 50, 000 .. M ≤ 10, 000 .. 保证 A[i] 在任何中间时刻的绝对值都不超过 10^9 ..)

ゆっくり読んでください ...

ZOJ 3539. Compress the String

Brief description:

… 定义某个字串的压缩算法,用一组字串压缩一个字符串。
方法是前面的字符串可以引用其后面出现的字符串然后在其原地扩展。。。

要求 s[1] 展开之后是原字符串,给定字符串数组的长度 N, 每个分解串的限制长度 Li。。
问是否存在无损压缩的方案。。
( .. . N < = 4, Li <= 4 .. .Sigma = 26 .. .) ゆっくり読んでください ...