526互联

Codeforces Round 889 (Div. 1)C. Expected Destruction（期望，动态规划）

发布时间 2023-08-27 19:54:32作者: XiCen

题目链接：https://codeforces.com/problemset/problem/1854/C

 

大致题意：

 

有一个集合S，和一个上界m；

 

现在每秒钟可以进行一次如下操作：

 

1：等概率的选取S中的一个元素x；

2：将x从S中移走；

3：如果x+1不大于m并且x+1不在S中，那么添加x+1在S里面

 

问期望多少秒钟后可以使得S为空集（答案模1e9+7）；

 

解题思路：

 

我们来观察这个过程，可以进行具体化一下：相当于，有n个木块向右移动，但俩个木块相撞，会消失一个；当木块移动到m+1会消失；

 

如果没有相撞，那么答案是固定（也就是每个木块的位置与m+1位置的差值的总和；

 

如果俩个木块在距离终点x的位置相撞的话，那么答案会减少x；

 

相撞一定是最开始的时候，相邻的俩木块来相撞；不然他们中间的木块会先和他们相撞；

 

由此我们进行dp；

 

设dp【x】【y】为 ai 为 x ， aj 为 y 的时候的概率；初始化dp【ai】【a（i+1）】为1；

 

对于x<y，以1/2的概率转移到dp【x+1】【y】和dp【x】【y+1】（我们不关心其他元素被选中，所以x或y的概率都是1/2被选中）；

 

对于dp【x】【x】我们将答案减去（m+1-x）*dp【x】【x】；

 

根据期望的线性性，我们可以把他们放一起dp；

 

故时间复杂度为：O（n^2)

 

代码：

#include<bits/stdc++.h>

const int N = 512, mod = 1e9 + 7;
int dp[N][N], a[N];

void Add(int& x, int a) { x += a, x >= mod &&(x -= mod); }
void Minus(int& x, int a) { x -= a, x < 0 && (x += mod); }

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int n, m;
    std::cin >> n >> m;

    int inv2 = (mod + 1 >> 1);

    for (int i = 1; i <= n; ++i)std::cin >> a[i];
    for (int i = 1; i < n; ++i)dp[a[i]][a[i + 1]] = 1;

    int ans = 0;
    for (int i = 1; i <= n; ++i)Add(ans, m + 1 - a[i]);

    for (int i = 1; i <= m; ++i)
    {
        Minus(ans, 1ll * dp[i][i] * (m + 1 - i) % mod);
        for (int j = i + 1; j <= m; ++j)
            Add(dp[i + 1][j], 1ll * dp[i][j] * inv2 % mod),
            Add(dp[i][j + 1], 1ll * dp[i][j] * inv2 % mod);
    }

    std::cout << ans << "\n";

    return 0;
}

 

通过观察，然后合理转化到一些不是那么抽象的情况来简化思考难度还是不错的：）