# Cow and Treats 題解

Cow and Treats 題解

在一年成功的牛奶生産後，Farmer John 獎勵他的奶牛們它們最喜歡的美味的草。

在田裡有 \(n\) 個機關的排成一行的草，每個機關的草有甜味 \(s_i\)。Farmer John 有 \(m\) 頭奶牛，每隻都有最喜歡的甜味 \(f_i\) 和饑餓值 \(h_i\)。他想要在奶牛選取兩個不相交的子集，分别在這行草的左側和右側排成一列。注意兩邊站多少奶牛是無關緊要的。

奶牛會按以下方式被喂：

Farmer John 會按照指定的順序依次喂奶牛。 -

在奶牛被喂的時候，它會徑直從一端走向另一端，一路上把甜味 \(s_i\) 和它喜愛的甜味 \(f_i\) 相同的草吃掉。

當它恰好吃了 \(h_i\) 機關的草，它會立即在原地停止不動并睡覺，這會使得其它奶牛無法通過這個位置（不論來自哪一側）。

如果一個奶牛遇到了一個睡着的奶牛或者它走到了整行草的最末尾都沒有吃飽，那麼它就會變得沮喪。Farmer John 絕對不想讓任何奶牛變得沮喪。

注意草不會長回來。并且為了防止奶牛沮喪，Farmer John 不必保證喂了所有奶牛。

驚人的是，Farmer John 已經發現睡着的奶牛是最滿足的。如果 Farmer John 安排的最優。求出最多的睡着的奶牛數，并求出在此情況下有多少種左右兩側奶牛的方案 Farmer John 可以選擇（對 \(10^9+7\) 取模）。隻要這個方案存在一種順序使得能不讓奶牛沮喪即可，Farmer John 具體如何安排是無關緊要的。

\(n,m\le 5000\)

首先，我們容易發現一個性質。

每種顔色的奶牛在序列中最多隻會出現兩次（一次從左邊出發，另一次從右邊出發）

我們枚舉一個分界點 \(i\) ，表示從第一頭出發的奶牛是從左邊出發的，且它到達的位置

然後對于每個分解點，我們對每種顔色分開處理，最後按照草排列的順序安排奶牛進入的順序

顯然，從右邊出發的奶牛最多走到 \(i+1\)

設\(slm_s\)表示從左邊到目前枚舉點 \(i\) 的甜味為 \(s\)的草的個數，\(srm_s\) 表示從右邊到 \(i+1\) 的甜味為 \(s\) 的草的個數，\(num[f][h]\) 表示要吃不多于 \(h\) 個機關甜味為 \(f\) 的草的牛的個數

首先考慮甜味為 \(s_i\) 的草，設 \(x=s_i\)

從左邊走滿足有 \(num[x][slm_x]-num[x][slm_x-1]\)頭奶牛符合條件

從右邊走滿足條件的牛有 \(num[x][srm_x]\)頭奶牛。但是如果 \(srm_x>=slm_x\)，左邊派出的奶牛也可能在右邊被派出，方案就重複了，是以右邊滿足的條件的牛數量應為 \(num[x][srm_x]\)

設左邊滿足條件的牛的數量為 \(sl\) ,右邊為 \(sr\)。

如果 \(sl=0\) 則不可能有滿足條件的方案，直接跳過

如果 \(sr=0\) 則該方案隻能貢獻一頭奶牛，方案數為 \(sl\)

否則 方案數為 \(sl*sr\) ，能貢獻兩頭奶牛

接下來考慮其他甜味的草。

對于顔色 \(j\) ，從左邊走滿足要求的有 \(num[j][slm_j]\) 頭，從右邊走有 \(num[j][srm_j]\)頭

接下來就很顯然了，就不講了

有一點是,當兩邊的符合條件的牛的數量都 \(>=2\) 時，方案數為 \(sl*sr-min(sl,sr)\)，這和我們上面的哪個 \(sl*sr\) 形式其實是一樣的