題目描述

傳送門

題解

這題n2$n^2$的暴力非常好想，預(yù)處理[l,r]有多少種食物sum(l,r)，然后f(i)=min{f(j)+sum(j+1,i)2}(1<=j<i)$f(i)=min/{f(j)+sum(j+1,i)^2/}(1<=j<i)$ 然后利用一點(diǎn)數(shù)學(xué)知識(shí)就有一個(gè)非常巧妙的優(yōu)化 這道題的答案是不會(huì)超過n的，所以要想最優(yōu)的話，枚舉的sum(l,r)不能超過n√$/sqrt n$

預(yù)處理PRe(i),nxt(i)表示與位置i食物相同的前一個(gè)/下一個(gè)的位置 pos(j)表示[pos(j)+1,i]一共有j種不同的食物 那么f(i)=min{f(pos(j))+j?j}(0<=j<=n√)$f(i)=min/{f(pos(j))+j*j/}(0<=j<=/sqrt n)$

如何維護(hù)pos(j)呢？ 記cnt(j)表示[pos(j),i]一共有多少種顏色 當(dāng)i從i-1轉(zhuǎn)移來時(shí)可以通過判斷位置i的食物的pre來計(jì)算cnt(j) 如果cnt(j)>j即不合法，那么pos(j)要向后移動(dòng)，直到把某一種顏色在區(qū)間中完全刪除，這中間可以用nxt來判斷

pos(j)單調(diào)移動(dòng)，總時(shí)間復(fù)雜度O(nn√)$O(n/sqrt n)$

代碼