题解 P2943 【[USACO09MAR]清理Cleaning Up】

先放一段 $BZOJ$ 的翻译,感觉更清楚: > 有 $n$ 头奶牛，每头那牛都有一个标号 $P_i$ 。现在 $Farmer John$ 要把这些奶牛分成若干段，定义每段的不河蟹度为：若这段里有 $k$ 个不同的数，那不河蟹度为 $k^2$。总不河蟹度就是所有段的总和.求最小总不河蟹度. emmmmmmm...... 您们的算法都好高深呀,我来个最弱的 ### 一种概率算法 > 我不太清楚这是不是模拟退火..我太菜了... (逃 首先易发现,对于一段相同的连续的元素,她们一定会被放到一个区间中.所以我们可以先对输入的数组进行去重. 设 $dp_i$ 为将前 $i$ 个数放在几个区间中,且第 $i$ 个数为区间结尾的最小花费 则 $$dp_i = min\{dp_{j-1}+dif_{[i,j]}\}$$ 也就是说,我们可以用 $dp_i$ 去转移所有 $dp_j\ (\ j \in (i,n]\ )$ ( $dif_{[i,j]}$ 表示 $[i,j]$ 中不同元素个数 ) 直接做会 $TLE$ 成 $70$ 分. 怎么办? 我们定义一个 $\color{Red}{\text{开心值}H}$ , 是一个 $[0,100]$ 的浮点数, 越高代表程序越开心.每次转移前都将 $H$ 设为 $100$. 当转移个五六千步时,如果当前状态太糟糕(不同元素太多了), $H$ 就会变小, 否则会变大(但变大的很小) 当我们的程序特别不开心(比如 $H<5$ 时) , 就会break掉,直接开始下一轮转移. 这能AC? 能. 代码很短:(这里只贴出关键部分) 需要开O2才能过,不开会90分 QAQ 但不得不说这是一种很好的骗分方法. ```cpp ld h; dp[0] = 0; For(i,n){ int u = dp[i-1]; int dif = 0; h = 100; Forx(j,i,n){ int v = a[j]; if(!have[v]){ have[v] = 1; dif++; } Mymin(dp[j],Sqr(dif)+u); if( Sqr(dif)+u >= n ) break; if( j-i > 5000 ) h *= 1.005 - (ld)dif / (ld)(j-i+1); if( h < 4 ) break; } Forx(j,i,n) have[a[j]] = 0; } ```