dp与概率期望

希望在开学前学完一遍dp

bzoj 3036 绿豆蛙的归宿-概率期望

算概率期望，然后算概率期望基本上是从后向前递推的。

题意

有一个连通的有向图，一只青蛙从1号到n号，节点与节点之间的连边有一条权重，问青蛙从1号节点到n号节点的距离的期望是多少？

题解

可以列出下面的公式

$F[u] = \frac{\sum_{1\le i\le deg[u]}F[i]+dist(u, i)}{k}$

然后通过跑反图就能得到正确的结果了

ac code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
struct Node{
    int v, next;
    int w;
}node[maxn<<1];
int n, m;
int head[maxn];
double ans[maxn];
int tot = 0;
void addedege(int u, int v, int w){
    node[tot].v = v;
    node[tot].w = w;
    node[tot].next = head[u];
    head[u] = tot++;
}
int deg[maxn], out[maxn];
int main()
{
    scanf("%d%d", &n, &m);
    int u, v, w;
    memset(head, -1, sizeof(head));
    memset(deg, 0, sizeof(deg)), memset(out, 0, sizeof(out));
    for(int i=1; i<=m; i++){
        scanf("%d%d%d", &u, &v, &w);
        addedege(v, u, w);
        deg[u]++, out[u]++;
    }
    queue<int> q;
    while(!q.empty()) q.pop();
    q.push(n);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i=head[x]; ~i; i=node[i].next){
            v = node[i].v;
            ans[v] += (ans[x]+node[i].w)/deg[v];
            out[v]--;
            if(out[v] == 0) q.push(v);
        }
    }
    printf("%.2lf\n", ans[1]);
    return 0;
}

codeforces 560E-计数DP

link

题意

一个h*w的棋盘上面，有n个黑点。问有多少种不同的方法，使得我们能够从左上角走到右下角

题解

若没有黑点，我们很快就能写出下面的方程：

$ans = C_{h+w-2}^{h-1}$

那么有黑点呢？

设$F[i]$为从左上角到$(x_i, y_i)$黑点方案数，并且中间不经过任何的黑点。

那么可以列出下面的方程：

$F[i] = C_{x_i-1+y_i-1}^{xi-1}-\sum{j=1}^{i-1}F[j]*C_{x_i-x_j+y_i-y_j}^{x_i-x_j}$

注意在减的过程中，是否会产生负数，然后再把它加回来。

还有一个需要注意的小技巧就是在终点的地方加了一个黑点，这也是为了方便讨论和计算。

注意它和F[i]巧妙的定义的融合。

ac code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
typedef long long ll;
const int mod = 1e9+7;
const int sz = 2005;
typedef pair<int, int> pii;
pii a[sz];
ll jc[maxn];
ll jcinv[maxn];
ll ans[sz];
ll powmod(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b&1){
            ans = ans*a%mod;
        }
        a = a*a%mod;
        b>>=1;
    }
    return ans;
}
ll calc(int n , int m){
    return 1ll*jc[n]*jcinv[m]%mod*jcinv[n-m]%mod;
}
int main()
{
    jc[0] = 1, jcinv[0] = 1;
    for(int i=1; i<=2e5; i++){
        jc[i] = jc[i-1]*i%mod;
        jcinv[i] = powmod(jc[i], mod-2);
    }
    int h, w, n;
    scanf("%d%d%d", &h, &w, &n);
    for(int i=1; i<=n; i++){
        scanf("%d%d", &a[i].first, &a[i].second);
    }
    a[n+1].first = h, a[n+1].second = w;
    sort(a+1, a+n+2);
    for(int i=1; i<=n+1; i++){
        ans[i] = calc(a[i].first+a[i].second-2, a[i].first-1);
        for(int j=1; j<i; j++){
            if(a[j].first>a[i].first||a[j].second>a[i].second){
                continue;
            }
            ans[i] = ans[i]-ans[j]*calc(a[i].first-a[j].first+a[i].second-a[j].second, a[i].first-a[j].first)%mod;
            ans[i] = (ans[i]+mod)%mod;
        }
    }
    printf("%lld\n", (ans[n+1]+mod)%mod);
    return 0;
}

poj 1737 计数DP+大数

题意

一个n个节点的图，每个节点都会有一个编号，因此虽然是同构的图，但若是节点编号之间的连接关系改变的话，那么也算是不同的方案数。问有多少种不同的图的方案数

题解

$F[i]$表示i个节点的无向图的连通的个数。

那么可以列出下面的方程：

$F[i] = 2^{\frac{i(i-1)}{2}} - \sum_{j=1}^{i-1}F[j]C_{i-1}^{j-1}2^{(i-j)*(i-j-1)/2}$

后面减掉的部分的思路是：

围绕1号节点为j个节点构成一张连通的无向图中，从剩余的i-1个点中选j-1个构成j连通图。

然后剩下的节点任意的进行边的连接。

列出算式之后，发现肯定是要使用大数的，但是现在懒得写了，就写一下思路吧。

HDU 5542 树状数组优化dp

题意

给一个数组，求有多少个严格单调增的长度为m的子序列，结果mod1e9+7

题解

ac code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3+10;
int n, m;
int a[maxn];
int dis[maxn];
ll c[maxn];
const int mod = 1e9+7;
int lowbit(int x){
    return (x&(-x));
}
void add(int x, ll val){
    while(x<=n+1){
        c[x] += val;
        c[x] %= mod;
        x += lowbit(x);
    }
}
ll query(int x){
    ll ans = 0;
    while(x>0){
        ans = (ans+c[x])%mod;
        x -= lowbit(x);
    }
    return ans;
}
ll ans[maxn][maxn];
int main(){
    int _;
    scanf("%d", &_);
    int kase = 1;
    while(_--){
        scanf("%d%d", &n, &m);
        for(int i=1; i<=n; i++){
            scanf("%d", &a[i]);
            dis[i] = a[i];
        }
        dis[0] = a[0] = -(1e9+10);
        //for(int i=0; i<=m; i++) ans[i][0] = 1;
        ans[0][0] = 1;
        sort(dis, dis+n+1);
        for(int i=0; i<=n; i++){
            a[i] = lower_bound(dis, dis+n+1, a[i])-dis+1;
        }
        for(int i=1; i<=m; i++){
            memset(c, 0, sizeof(c));
            add(a[0], ans[i-1][0]);
            for(int j=1; j<=n; j++){
                ans[i][j] = query(a[j]-1);
                add(a[j], ans[i-1][j]);
            }
        }
        ll last = 0;
        for(int i=1; i<=n; i++){
            last = (last+ans[m][i])%mod;
        }
        printf("Case #%d: %lld\n", kase++, last);
    }
}

未解决的问题

本文标题:dp与概率期望

文章作者:Babydragon

发布时间:2019-02-17, 14:07:00

最后更新:2019-02-17, 21:02:17

原始链接:http://baolintian.github.io/2019/02/17/dp与概率期望/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. bzoj 3036 绿豆蛙的归宿-概率期望
    1. 1.1. 题意
    2. 1.2. 题解
    3. 1.3. ac code
  2. 2. codeforces 560E-计数DP
    1. 2.1. 题意
    2. 2.2. 题解
    3. 2.3. ac code
  3. 3. poj 1737 计数DP+大数
    1. 3.1. 题意
    2. 3.2. 题解
  4. 4. HDU 5542 树状数组优化dp
    1. 4.1. 题意
    2. 4.2. 题解
    3. 4.3. ac code
  5. 5. 未解决的问题
{{ live2d() }}