题目分析

性质

  1. 所有积水高度小于等于 1 号点的点可以直接丢掉。
    所以,将留下来的水的高度都改成其原本的高度-1 号点高度,最后答案再加上 1 号点的高度。
  2. 假如被要求进行两次合并,有两杯水 $h _ 1<h _ 2$,则一定先合并低的,再合并高的。
    证明:先合并低的:$\frac{1}{2}(\frac{1}{2} h _ 1+ h _ 2)=\frac{1}{4} h _ 1+\frac{1}{2} h _ 2$,先合并高的:$\frac{1}{2} h _ 1 + \frac{1}{4} h _ 2$。
  3. 若有一部分水合并了,一部分没有,那么被合并的水一定是最高的几杯。

将所有留下来的水从低到高排序,设 $h _ i$表示第 $i$杯水的高度,$s _ i$表示前 $i$杯水的高度前缀和。

合并操作一定是堆在最后面的一段一段的区间,从前往后合并。

设 $f(i,j)$表示前 $j$杯水合并了 $i$次。

$f(i,j)=max(\frac{f(i-1,k)+s _ j-s _ k}{j-k+1})$

观察这个式子,发现是点 $(k-1,s _ k – f(i-1,k))$和点 $(j, s _ j)$构成的直线的斜率。

用单调队列维护点 $(k-1,s _ k – f(i-1,k))$构成的下凸壳。因为点 $(j, s _ j)$的 y 坐标随 x 坐标递增,所以找最优决策时,将队首一段不会构成最优决策的点的弹出,队首就是最优决策。

代码

那个 600 多行的高精度小数类就直接删掉了……只要记得将开头的 const int PREC=后面的数字改为 3000 以上即可。

将每一步的决策用 short 记录下来,然后用高精度小数类再算一次答案。

using namespace std;
#define RI register int
typedef long double db;
typedef long long LL;
const int N=8005;
Decimal ans;
int orzyyb,n,K,P,kpos;db kans;
int h[N],qid[N];LL s[N];short las[N][N];db f[2][N];
struct point{db x,y;}que[N];
point operator - (point A,point B) {return (point){A.x-B.x,A.y-B.y};}
db operator * (point A,point B) {return A.x*B.y-B.x*A.y;}

Decimal getans(int x,int y) {
    if(x==0) return 0;
    return (getans(x-1,las[x][y])+s[y]-s[las[x][y]])/(y-las[x][y]+1);
}

int main() {
    scanf("%d%d%d",&orzyyb,&K,&P);
    scanf("%d",&h[0]);
    for(RI i=1;i<orzyyb;++i) {
        int x;scanf("%d",&x);
        if(x>h[0]) h[++n]=x-h[0];
    }
    sort(h+1,h+1+n);
    for(RI i=1;i<=n;++i) s[i]=s[i-1]+h[i];
    if(K>n) K=n;
    for(RI i=1,t=1;i<=K;++i,t^=1) {
        int he=1,ta=1;
        que[1]=(point){(db)i-2,(db)s[i-1]-f[t^1][i-1]},qid[1]=i-1;
        for(RI j=i;j<=n;++j) {
            point P=(point){(db)j,(db)s[j]};
            while(he<ta&&(P-que[he+1])*(P-que[he])<0) ++he;
            las[i][j]=qid[he],f[t][j]=(db)(P.y-que[he].y)/(db)(P.x-que[he].x);
            P=(point){(db)j-1,(db)s[j]-f[t^1][j]};
            while(he<ta&&(que[ta]-que[ta-1])*(P-que[ta-1])<0) --ta;
            ++ta,que[ta]=P,qid[ta]=j;
        }
        if(f[t][n]>=kans) kans=f[t][n],kpos=i;
    }
    ans=getans(kpos,n)+h[0];
    cout<<ans.to_string(P<<1)<<endl;
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

4 条评论

Qiuly · 2019年4月30日 10:02 下午

n^2 的复杂度或许过高了吧,加上常数估计后面几个点会不会被卡掉… 啊

听说最后一个结论可以大大的优化,但是结论本身很迷。

    boshi · 2019年5月4日 11:24 上午

    litble 的意思是 $O(n^2)$用低精度数算一遍,记录下转移,最后 $O(np)$用高精度数计算,这样避免了 $Dp$时使用高精度数,从而可以不用最后的结论的优化。

      Qiuly · 2019年5月4日 12:49 下午

      哦… 难怪

    Rayment · 2019年5月4日 11:25 上午

    其实跑得很快,在 [UOJ269] 如何优雅地求和 里面 $O(n^2)$ 可以跑过 $n=20000$

发表评论

电子邮件地址不会被公开。 必填项已用*标注