[BZOJ1584][Usaco2009 Mar]Cleaning Up 打扫卫生（dp+数学相关优化）

题目描述

传送门

题解

这题n2$n^2$的暴力非常好想，预处理[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)$ 然后利用一点数学知识就有一个非常巧妙的优化 这道题的答案是不会超过n的，所以要想最优的话，枚举的sum(l,r)不能超过n√$/sqrt n$

预处理PRe(i),nxt(i)表示与位置i食物相同的前一个/下一个的位置 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)$

如何维护pos(j)呢？ 记cnt(j)表示[pos(j),i]一共有多少种颜色 当i从i-1转移来时可以通过判断位置i的食物的pre来计算cnt(j) 如果cnt(j)>j即不合法，那么pos(j)要向后移动，直到把某一种颜色在区间中完全删除，这中间可以用nxt来判断

pos(j)单调移动，总时间复杂度O(nn√)$O(n/sqrt n)$

代码