前置知识:连续段 dp
题目链接:P2612 [ZJOI2012] 波浪
\[|P_1 - P_2| + |P_2 - P_3| + |P_3 - P_4| + ... + |P_{n-1} + P_n| \]随机一个 \(1\) 到 \(n\) 的排列 \(P_{1...n}\),问以下式子的值 \(\le m\) 的概率是多少?
输出一个答案表示概率。保留 \(k\) 位小数。
对于 \(40%\) 的数据,\(n \le 50,k \le 30\)。
对于 \(60%\) 的数据,\(n \le 100,k \le 8\)。
对于全部数据,\(0 \le m \le 2147483647\)。
首先不难想到按位 dp,但是由于是个排列还要状压,肯定行不通。
所以考虑依次放数字 \(1,2,...,n\)。此时不难发现,每个状态是一个连续段,所以考虑连续段 dp。
设 \(dp_{i,j,k,p}\) 表示放了 \(i\) 个数字,有 \(j\) 个连续段,贡献为 \(k\),有 \(p\) 个端点被确定了的方案数。由于算的是概率,所以最后乘上 \(n!\) 即可。
但是为什么可以设贡献为状态的呢?
Trick:先把绝对值去掉,然后把每个项拆开成 \(i\) 和 \(i+1\) 的贡献。
由于我们把数字从小往大放,所以绝对值已经去掉了。然后每放一个数,就可以算出该数的贡献了。
然后就直接上连续段 dp(需要一维 \(p\) 因为 \(1\) 和 \(n\) 只有一次贡献):
连续段 dp
令 \(t = dp[i-1][j][k][p]\)。
1. 产生新的段
- 不产生新端点(即把数放在 \(2\) 到 \(n-1\) 之间)
- 产生新端点(即把数放在 \(1\) 或 \(n\))
2. 接在某个已有段的两端
- 不产生新端点(即把数放在 \(2\) 到 \(n-1\) 之间)
- 产生新端点(即把数放在 \(1\) 或 \(n\))
3. 作为介质,合并两个已有段
\[dp[i][j-1][k+2i][p] \gets t \times (j-1) \]时间复杂度 \(\mathcal{O}(n^4)\),因为 \(j\) 的范围是 \(\mathcal{O}(n^2)\) 的。
精度问题
但是由于这题的精度要求比较高,所以可以 dp 到 \(i\) 时就 \(\div i\)。(不知道怎么实现可以看代码)另外,记得用 long double
。
然后交上去之后:
精度不够啊。
于是考虑换成 __float128
:
太慢了 QAQ。
难道就没有什么好的办法了吗?
你猜为什么我放了点分治的 tag?
没错!数据点分治!注意到数据范围:
对于 \(40%\) 的数据,\(n \le 50,k \le 30\)。
对于 \(60%\) 的数据,\(n \le 100,k \le 8\)。
所以如果 \(k \le 8\) 就用 long double
,否则用 __float128
。然后就可以通过了。
另外由于数据点分治之后要用不同的 type 存 dp,所以推荐一种比较方便的 template写法。
代码
// Author: AquariusZhao
#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = 5005 << 1, Pre = 5000, Mx = 10000;
const long double eps = 1e-20;
int n, m, k;
long double dp1[2][N][M][3];
__float128 dp2[2][N][M][3];
template <class T>
void solve(T dp[2][N][M][3])
{
int cur = 0, pre = 1;
dp[cur][0][Pre][0] = 1;
for (int i = 1; i <= n; i++)
{
swap(cur, pre);
memset(dp[cur], 0, sizeof(dp[cur]));
for (int j = (i > 1); j <= i; j++)
for (int k = 0; k <= Mx; k++)
for (int p = 0; p <= 2; p++)
{
auto from = dp[pre][j][k][p];
if (!from)
continue;
// new
if (k >= 2 * i)
dp[cur][j + 1][k - 2 * i][p] += from * (j + 1 - p) / i;
if (k >= i && p < 2)
dp[cur][j + 1][k - i][p + 1] += from * (2 - p) / i;
if (j == 0)
continue;
// end
dp[cur][j][k][p] += from * (2 * j - p) / i;
if (k + i <= Mx && p < 2)
dp[cur][j][k + i][p + 1] += from * (2 - p) / i;
if (j == 1)
continue;
// mid
if (k + 2 * i <= Mx)
dp[cur][j - 1][k + 2 * i][p] += from * (j - 1) / i;
}
}
T ans = 0;
for (int k = m; k <= Mx - Pre; k++)
ans += dp[cur][1][Pre + k][2];
if (ans + eps >= 1)
{
cout << "1." << string(k, '0');
return;
}
cout << "0.";
for (int i = 1; i <= k; i++)
{
ans *= 10;
putchar(int(ans + (i == k) * 0.5) + '0');
ans -= int(ans);
}
}
int main()
{
#ifdef aquazhao
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin >> n >> m >> k;
if (k <= 8)
solve(dp1);
else
solve(dp2);
return 0;
}
标签:le,cur,题解,times,ZJOI2012,P2612,端点,gets,dp
From: https://www.cnblogs.com/avalaunch/p/18543732