首页 > 其他分享 >关于转移中需要根据期望相对大小进行分讨的期望 dp

关于转移中需要根据期望相对大小进行分讨的期望 dp

时间:2023-03-23 19:56:58浏览次数:57  
标签:期望 迭代 int text sum vis 分讨 dp

转移式形如 \(\displaystyle f_i = \sum_{f_i > f_j} g(i, j) f_j + \sum_{f_i < f_j} h(i, j) \boldsymbol{f_i}\)。

考虑初始化所有 \(f_i\) 为正无穷,化一下式子后发现 \(f_j > f_i\) 时仅仅个数而非具体值时被在意的,则当更新 \(f_j < f_i\) 时能出现额外的、从第二个式子变为第一个式子而产生的贡献。因此按 \(f_i\) 的大小排序并动态处理。每次取出最优的 \(f_i\) 更新其它点,容易发现这样无后效性。

P4745 [CERC2017]Gambling Guide

给定一张无向图,一个人从 \(1\) 出发,站在每个点时每单位时间以均等概率开放一条出边,人可以选择走过这条边或等下一单位时间。求最优策略下到达 \(n\) 的期望时间。

\(n, m \leq 3 \cdot 10^5\)

套路性地设从 \(i\) 到 \(n\) 最佳方案的期望为 \(f_i\),只考虑一次的选择。如果走过去期望小于留下来,显然该走;不然显然该留。

\[\begin{aligned} f_u &= 1 + \dfrac{1}{\text{deg}_u} \sum_{(u, v) \in E} \min\{f_u, f_v\} \\ \text{deg}_u f_u&= \text{deg}_u + f_u \sum_{(u, v) \in E} [f_v > f_u] + \sum_{(u, v) \in E} [f_v < f_u] f_v \\ f_u &= \dfrac{\text{deg}_u + \sum_{(u, v) \in E} [f_v < f_u] f_v}{\sum_{(u, v) \in E} [f_v < f_u] } \end{aligned} \]

注意到用 \(f_v < f_u\) 迭代更新 \(u\) 时只会让答案更优,尝试寻找无后效性的迭代方式,则能保证复杂度,否则暴力计算复杂度乘一个 \(n\)。

尝试从小到大计算,则当处理完前 \(i\) 大的期望值时,当前最小的 \(f_u\) 一定是所求第 \(i+1\) 小。

为什么?容易发现此时 \(f_u\) 已经被计算完毕,且其它不在前 \(i\) 大的 \(f_v\) 一定大于它的准确值,从而大于现在的 \(f_u\)。

可以直接迭代 \(n\) 轮每次找最小值更新,可以跑一个 dij 优化每轮找的过程。其实 dij 不也是这样,贪心找全局最小值,使计算一个点对其它点的贡献时它本身已经被计算完毕。

这里依赖了什么呢?好像只有迭代一轮能使答案能优,以及可以快速算把 \(v\) 对 \(u\) 的贡献从一类放到另一类时 \(f_u\) 的变化量,后者满足可减性的式子都能这样干。

其实说完这题后这类题感觉都差不多了,但是做完下一题我才真正理解直接找到全局最小值的正确性。

#include <bits/stdc++.h>
using namespace std;
const int M = 3e6 + 5;
vector<int> e[M];
priority_queue<pair<double, int> > q;
double f[M], sm[M]; int n, m, cnt[M];
bool vis[M];
void dij() {
  q.push({0, n});
  while (!q.empty()) {
    int u = q.top().second; q.pop();
    if (vis[u]) continue; vis[u] = 1;
    for (auto v : e[u]) {
      if (!vis[v]) {
        ++cnt[v], sm[v] += f[u];
        f[v] = (e[v].size() + sm[v]) / cnt[v];
        q.push({-f[v], v});
      }
    }
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v; scanf("%d %d", &u, &v);
    e[u].push_back(v), e[v].push_back(u);
  }
  dij(); printf("%.6lf\n", f[1]);
}

咦,最短路是不是也是这样的(

CF605E Intergalaxy Trips

给定一张完全图,\(i \to j\) 的边每天以 \(p_{i, j}\) 的概率出现。站在 \(i\),每天可以走过一条存在的边或什么都不做。求最优策略下从 \(1\) 走到 \(n\) 的天数的期望。

\(n \leq 300\)

仍然采用与上题一样的设状态法。

显然每天要去期望最小的能到达的点,如果期望最小的点大于当前点则不动。

\[f_i = \sum_{f_j < f_i} p_{i, j} f_j \prod_{f_k < f_j} (1 - p_{i, k}) + f_i \prod_{f_j < f_i} (1 - p_{i, j}) + 1 \\ f_i = \dfrac{1 + \sum_{f_j < f_i} p_{i, j} f_j \prod_{f_k < f_j} (1 - p_{i, k})}{1 - \prod_{f_j < f_i} (1 - p_{i, j})} \]

采用与上一题一样的迭代就行了。从优到劣迭代,即按 \(f\) 从大到小迭代。

分子上的求和用了分母的结果以快速求出,感觉这里挺厉害。不过不能快速求不影响这样能做。

#include <bits/stdc++.h>
using namespace std;
const int M = 1005;
double f[M], g[M], h[M];
int n; double p[M][M];
bool vis[M];
void upd(int j) {
  vis[j] = 1;
  for (int i = 1; i <= n; i++) if (!vis[i]) {
    g[i] += p[i][j] * f[j] * h[i], h[i] *= (1 - p[i][j]);
    f[i] = g[i] / (1 - h[i]);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= n; j++)
      scanf("%lf", &p[i][j]), p[i][j] /= 100;
  for (int i = 1; i <= n; i++)
    f[i] = g[i] = h[i] = 1;
  f[n] = g[n] = 0; upd(n);
  for (int i = 1; i < n; i++) {
    int t = 0;
    for (int j = 1; j <= n; j++) 
      if (!vis[j] && (f[j] < f[t] || (!t))) 
        t = j;
    upd(t);
  }
  printf ("%.11lf\n", f[1]);
}

在学校里登 cnblogs 太麻烦了 /tuu 终于又感到了 Luogu Blog 的温暖。

标签:期望,迭代,int,text,sum,vis,分讨,dp
From: https://www.cnblogs.com/purplevine/p/17248670.html

相关文章