题面
之前别的学校模拟赛的题吧, 显然是没有上 oj 的
挂个 pdf
题面下载
算法
概率类型的题目, 这一题看着像概率 dp, 是不会的
先按照一般的思路, 从前往后考虑操作
设 \(f_{i, j}\) 为考虑了前 \(i\) 步操作, 当前位置为 \(j\) 的概率
考虑状态转移
对于操作的每一个位置, 显然其会被之前的位置所影响, 也显然可以影响后面的位置
\[f_{i, j} = \sum \left[f_{i - 1, j} \times P_{dont \text{ } move} + f_{i - 1, j - Move_i} \times \left(1 - P_{dont \text{ } move} \right)\right]
\]
当然实现的时候最好使用刷表法
但是写出来之后是 \(\rm{WA} \text{ } 12pts\) 的, \(\rm{why}\)?
画表分析一下, 当一条路径重复经过了同一个点, 那么这个 dp 方程将会两次计算这种情况对这个点的贡献, 考虑去重
人类智慧发现, 倒推操作时, 即使现在重复经过了一个点, 也不会影响结果(事实上我不知道为什么)
于是完成
代码
#include <bits/stdc++.h>
using namespace std;
#define int long longconst int N = 5005, MOD = 1e9 + 7;int qpow(int x, int y)
{int cnt = 1;for (; y; y >>= 1){if (y & 1)cnt = cnt * x % MOD;x = x * x % MOD;}return cnt;
}int n, p, a[N], dp[N][N * 2], ans;signed main()
{cin >> n >> p;p = p * qpow(100, MOD - 2) % MOD;int ip = (1 - p + MOD) % MOD;for (int i = 1; i <= n; i++)cin >> a[i];dp[0][n] = 1;for (int i = 1; i <= n; i++){for (int j = n - i + 1; j <= n + i - 1; j++){dp[i][j] = (dp[i][j] + p * dp[i - 1][j]) % MOD;dp[i][j + a[n - i + 1]] = (dp[i][j + a[n - i + 1]] + ip * dp[i - 1][j]) % MOD;}dp[i][n] = 1;}for (int i = 0; i <= 2 * n; i++)cout << dp[n][i] << " ";cout << "\n";return 0;
}/*
5 83
1 -1 -1 1 1
*/
总结
dp 推不出来? 考虑换一下顺序
