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 .. .) ゆっくり読んでください ...