BZOJ4899: 记忆的轮廓【概率期望DP】【决策单调性优化DP】

Description

通往贤者之塔的路上，有许多的危机。

我们可以把这个地形看做是一颗树，根节点编号为1，目标节点编号为n，其中1-n的简单路径上，编号依次递增，

在[1,n]中，一共有n个节点。我们把编号在[1,n]的叫做正确节点，[n+1,m]的叫做错误节点。一个叶子，如果是正

确节点则为正确叶子，否则称为错误叶子。莎缇拉要帮助昴到达贤者之塔，因此现在面临着存档位置设定的问题。

为了让昴成长为英雄，因此一共只有p次存档的机会，其中1和n必须存档。被莎缇拉设置为要存档的节点称为存档

位置。当然不能让昴陷入死循环，所以存档只能在正确节点上进行，而且同一个节点不能存多次档。因为通往贤者

之塔的路上有影响的瘴气，因此莎缇拉假设昴每次位于树上一个节点时，都会等概率选择一个儿子走下去。每当走

到一个错误叶子时，再走一步就会读档。具体的，每次昴到达一个新的存档位置，存档点便会更新为这个位置（假

如现在的存档点是i，现在走到了一个存档位置j>i，那么存档点便会更新为j）。读档的意思就是回到当前存档点

。初始昴位于1，当昴走到正确节点n时，便结束了路程。莎缇拉想知道，最优情况下，昴结束路程的期望步数是多

少？

Input

第一行一个正整数T表示数据组数。

接下来每组数据，首先读入三个正整数n,m,p。

接下来m-n行，描述树上所有的非正确边（正确边即连接两个正确节点的边）

用两个正整数j，k表示j与k之间有一条连边，j和k可以均为错误节点，也可以一个为正确节点另一个为错误节点。

数据保证j是k的父亲。

50<=p<=n<=700，m<=1500，T<=5。

数据保证每个正确节点均有至少2个儿子，至多3个儿子。

Output

T行每行一个实数表示每组数据的答案。请保留四位小数。

Sample Input

1

3 7 2

1 4

2 5

3 6

3 7

Sample Output

9.0000

思路

发现其实还是在一条链上进行dp，剩下的分支都可以直接与处理做掉

首先求出从每个点进入坏点返回存档点的期望步数\(f_{i}\)

然后可以算一下以每一个点i为最新存档点到点j的期望步数（途中没有存档点）\(w_{i,j}\)

首先设\(cur\)为从\(j-1\)到\(j\)的期望步数

可以得到\(cur=\frac{1}{d_{j-1}}+\frac{d_{j-1}-1}{d_{j-1}}*(f_{j-1}+w_{i,j-1}+cur)\)

又因为\(w_{i,j}=w_{i,j-1}+cur\)

所以\(w_{i,j}=w_{i,j-1} * d_{j-1} + f_{j-1} * (d_{j-1} - 1) + 1\)

然后就可以dp了

记录\(dp_{i,j}\)表示前i个点选了j个存档位置，最新的存档位置是i的最小期望步数

我们想用决策单调性优化，所以就要从

\(dp_{j,x}+w_{j,i}\le dp_{k,x}+w_{k,i}(k<j)\)

推到

\(dp_{j,x}+w_{j,i+1}\le dp_{k,x}+w_{k,i+1}(k<j)\)

也就是说要证明\(w_{k,i}-w_{j,i}\le w_{k,i+1}-w_{j,i+1}\)

转化成\(w_{k,i}+w_{j,i+1}\le w_{k,i+1}+w_{j,i}\)

其中\(k<j\le i<i+1\)

然后对于w

我们来推一下式子看看是不是

\(w_{i,j}+w_{i+1,j+1}\le w_{i+1,j}+w_{i,j+1}\)

左边\(w_{i,j}+w_{i+1,j+1}=w_{i,j}+w_{i+1,j}*d_j+f_j*(d_j-1)+1\)

右边\(w_{i+1,j}+w_{i,j+1}=w_{i+1,j}+w_{i,j}*d_j+f_j*(d_j-1)+1\)

发现是满足的，然后就直接按照套路维护就可以了

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

const int N = 2010;

int n, m, p, d[N];

vector<int> g[N];

ld f[N], w[N][N], dp[N][N];

struct Node {

  int pos, l, r;

  Node() {}

  Node(int pos, int l, int r): pos(pos), l(l), r(r) {}

} que[N];

void init() {

  for (int i = 1; i <= n; i++) {

    for (int j = 1; j <= n; j++) {

      w[i][j] = 0;

      dp[i][j] = 1e9;

    }

  }

  for (int i = 1; i <= m; i++) {

    f[i] = 0;

    d[i] = 0;

    g[i].clear();

  }

}

void dfs(int u) {

  if (!(signed) g[u].size()) {

    f[u] = 1;

    return;

  }

  for (int i = 0; i < (signed) g[u].size(); i++) {

    int v = g[u][i];

    dfs(v);

    f[u] += (f[v] + 1.0) / (1.0 * d[u]);

  }

}

ld calc(int i, int j, int k) {

  return dp[j][k - 1] + w[j][i];

}

int find(Node a, int b, int k) {

  int l = a.l, r = n, res = n;

  while (l <= r) {

    int mid = (l + r) >> 1;

    if (calc(mid, a.pos, k) >= calc(mid, b, k)) res = mid, r = mid - 1;

    else l = mid + 1;

  }

  return res;

}

void solve() {

  scanf("%d %d %d", &n, &m, &p); p--;

  init();

  for (int i = 1; i <= m - n; i++) {

    int u, v; scanf("%d %d", &u, &v);

    g[u].push_back(v);

    ++d[u];

  }

  for (int i = n; i >= 1; i--) dfs(i);

  for (int i = 1; i <= n - 1; i++) ++d[i];

  for (int i = n; i >= 1; i--) {

    for (int j = i + 1; j <= n; j++) {

      w[i][j] = w[i][j - 1] * d[j - 1] + f[j - 1] * (d[j - 1] - 1) + 1;

    }

  }

  dp[1][1] = 0;

  for (int i = 2; i <= p; i++) {

    int ql = 1, qr = 1;

    que[ql] = Node(i - 1, i - 1, n);

    for (int j = i; j < n; j++) {

      if (ql <= qr && ++que[ql].l > que[ql].r) ql++;

      dp[j][i] = calc(j, que[ql].pos, i);

      if (ql <= qr && calc(n, que[qr].pos, i) <= calc(n, j, i)) continue;

      while (ql <= qr && calc(que[qr].l, que[qr].pos, i) >= calc(que[qr].l, j, i)) qr--;

      if (ql > qr) {

        que[++qr] = Node(j, j, n);

      } else {

        int cur = find(que[qr], j, i);

        que[qr].r = cur - 1;

        que[++qr] = Node(j, cur, n);

      }

    }

  }

  ld ans = 1e9;

  for (int i = 1; i < n; i++) {

    ans = min(ans, dp[i][p] + w[i][n]);

  }

  printf("%.4Lf\n", ans);

}

int main() {

#ifdef dream_maker

  freopen("input.txt", "r", stdin);

#endif

  int T; scanf("%d", &T);

  while (T--) solve();

  return 0;

}

巴特西