interestingLSY 的博客

interestingLSY 的博客

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

posted on 2018-08-29 16:56:30 | under 题解 |

先放一段 $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

但不得不说这是一种很好的骗分方法.

    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;
    }