?

首先，分析一下這個貓和鼠

貓每局都可以追老鼠一步或者兩步，但是除了最后的一步，肯定走兩步快些....

既然貓走的步數總是比老鼠多，那么它們的距離在逐漸縮小（如果這題只能走一步反而不能做了...）

貓不知道老鼠下一步走哪里，貓走的時候依據的是老鼠當前的位置

?

明顯，貓走的位置沒有什么規律可言（即使有規律還是會預處理啊.....）

我們可以在$O(n^2 + nm)$的復雜度內預處理出$s(i, j)$表示貓在$i$，老鼠在$j$時，貓下一步的位置...

?

直接設$f(i, j)$表示貓在$i$，老鼠在$j$時貓吃到老鼠的期望步數

那么有$f(i, i) = 0$

并且$f(i, s(i, j)) = 1，f(i, s(s(i, j), j)) = 1 (i \neq j)$

其余情況下$f(i, j) = \sum\limits_{v = j | e(j, v)} \frac{f(s(s(i, j), j), v) + 1}{du[j] + 1}$

由于貓鼠距離減小，因此轉移具有拓撲序

可以根據貓鼠距離排序轉移，也可以直接$dfs$

由于$dfs$好寫，因此這里選擇$dfs$

復雜度$O(n^2 + nm)$

#include <cstdio> #include <iostream> using namespace std;extern inline char gc() {static char RR[23456], *S = RR + 23333, *T = RR + 23333;if(S == T) fread(RR, 1, 23333, stdin), S = RR;return *S ++; } inline int read() {int p = 0, w = 1; char c = gc();while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); }while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc();return p * w; }#define de double #define sid 1005 #define eid 5005 #define ri register intint n, m, s, t, cnp; int cap[eid], nxt[eid], node[eid], q[eid]; int du[sid], dis[sid][sid], nx[sid][sid]; de f[sid][sid];void adeg(int u, int v) {du[u] ++;nxt[++ cnp] = cap[u]; cap[u] = cnp; node[cnp] = v; }#define cur node[i] void Pre() {for(ri u = 1; u <= n; u ++) {int fr = 1, to = 0;q[++ to] = u; dis[u][u] = 0;while(fr <= to) {int o = q[fr ++];for(ri i = cap[o]; i; i = nxt[i])if(dis[u][cur] == 1e5)dis[u][cur] = dis[u][o] + 1, q[++ to] = cur;}}for(ri u = 1; u <= n; u ++)for(ri v = 1; v <= n; v ++) {int w = 1e5;for(ri i = cap[u]; i; i = nxt[i])if(dis[cur][v] < w || (dis[cur][v] == w && nx[u][v] > cur))nx[u][v] = cur, w = dis[cur][v];} }de dfs(int a, int b) {if(f[a][b] != -1) return f[a][b];if(a == b) return f[a][b] = 0;int to = nx[a][b], toto = nx[to][b];if(to == b || toto == b) return f[a][b] = 1;f[a][b] = 0;for(int i = cap[b]; i; i = nxt[i])f[a][b] += (dfs(toto, cur) + 1) / (de)(du[b] + 1);f[a][b] += (dfs(toto, b) + 1) / (de)(du[b] + 1);return f[a][b]; }int main() {n = read(); m = read();s = read(); t = read();for(ri i = 1; i <= m; i ++) {int u = read(), v = read();adeg(u, v); adeg(v, u);}for(ri i = 1; i <= n; i ++)for(ri j = 1; j <= n; j ++)dis[i][j] = 1e5, f[i][j] = -1;Pre();printf("%.3lf\n", dfs(s, t));return 0; }

?

轉載于:https://www.cnblogs.com/reverymoon/p/9513915.html

總結

以上是生活随笔為你收集整理的luoguP4206 [NOI2005]聪聪与可可 期望概率DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。