CF643C Levels and Regions

· · 题解

\text{Description}

有一种电子游戏，它由 n 个关卡组成，每个关卡都被赋予了一个值 t_i。

现在，你要将这些关卡分成 k 个级别，每个级别 j 对应了一段连续的关卡 [l_j,r_j]，且必有 l_j\leq r_j。任何一个关卡在且仅在一个级别中。

然后，一名玩家将会从第 1 个关卡，按顺序一直刷到第 n 个关卡。当他打到第 i 个关卡时，设这个关卡所在的级别是 j，则他有 \dfrac{t_i}{\sum\limits_{x=l_j}^{i}t_x} 的概率在1小时内AC这个关卡，然后进入下一关；或者没有 AC 这个关卡（但仍然花了 1 小时），还得再次挑战这个关卡。

你需要找到一种划分方法，使得该玩家期望 AK 该游戏的期望时间最小。输出这个最小的期望时间。

\text{Solution}

一道乍看很吓人但是仔细想想并不难的小清新 dp 题。
有一个期望相关的常用结论：若一件事做成的概率是 p，那么做成这件事需要的期望次数是 \dfrac{1}{p}。
证明：设期望次数为 x，讨论第一次做成或者没做成，就有：

x=(p\times0+(1-p)\times x)+1

移项即可得。

回到本题。
显然不同段之间互相独立。
设 sum_i=\sum_{j=1}^i t_j。
那么本题 (l,r) 区间划分成一段完成的期望次数就是：

\sum_{i=l}^r \frac{sum_i-sum_{l-1}}{t_i}

也就是：

\sum_{i=l}^r \frac{sum_i}{t_i}-sum_{l-1}\times\sum_{i=l}^r \frac{1}{t_i}

对 \sum_{i=l}^r \dfrac{sum_i}{t_i} 和 \sum_{i=l}^r \dfrac{1}{t_i} 分别求前缀和，我们就可以 O(1) 转移了。
然后直观感受可以发现，这个东西是满足决策单调性的。
感性理解一下就是要使全局尽可能小，前面的 \sum_{i=l}^r \dfrac{sum_i}{t_i} 全合起来后是定值，后面多一个元素的时候，\sum_{i=l}^r \dfrac{1}{t_i} 变大，那么为了多减一些，sum_{l-1} 的值应该相应的变大（或者至少不应该变小），所以转移点有单调性的。
直接上分治即可，时间复杂度 O(nk\log n)。 （看题解的大佬这题也可以斜优做把 log 去掉）

\text{Code}

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=2e5+100;
#define ll long long
inline ll read(){
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}

int n,m;
double sum[N],t[N];
double s1[N],s2[N];
inline double calc(int l,int r){
  return (s1[r]-s1[l-1])-sum[l-1]*(s2[r]-s2[l-1]);
}
double dp[52][N];
void solve(int k,int l,int r,int tl,int tr){
  if(l>r) return;
  int mid=(l+r)>>1,pl(0);
  for(int i=tl;i<=min(mid-1,tr);i++){
    double w=dp[k-1][i]+calc(i+1,mid);
    if(w<dp[k][mid]){
      dp[k][mid]=w;pl=i;
    }
  }
  solve(k,l,mid-1,tl,pl);solve(k,mid+1,r,pl,tr);
  return;
}
signed main(){
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
  n=read();m=read();
  for(int i=1;i<=n;i++){
    t[i]=read();
    sum[i]=sum[i-1]+t[i];
    s1[i]=s1[i-1]+sum[i]/t[i];
    s2[i]=s2[i-1]+1.0/t[i];
  }
  for(int i=0;i<=m;i++){
    for(int j=0;j<=n;j++) dp[i][j]=2e18;
  }
  dp[0][0]=0;
  for(int k=1;k<=m;k++) solve(k,1,n,0,n-1);
  printf("%lf\n",dp[m][n]);
  return 0;
}
/*

*/