正文

loj6171/bzoj4899记忆的轮廊（期望dp+优化）

人活着就是为了Chelly  人活着就是为了Chelly  2022-09-07  195

关键词：

题目：

https://loj.ac/problem/6171

分析：

设dp[i][j]表示从第i个点出发（正确节点），还可以有j个存档点（在i点使用一个存档机会），走到终点n的期望步数

那么

a[i][k]表示i点为存档点，从i点走到k点（正确节点）的期望步数（中间没有其它存档点）

那么a[i][j]可以递推预处理出

其中g[v]表示从一个错误节点v开始走，期望走g[v]步会读档

解方程可以解出

s[j-1]就是点j-1出去的所有错误儿子的g[v]之和

那么接下来只要知道如何求g[v]就行了

这个直接dfs一遍就行了

好，那么现在我们的主dp就可以求解了

但是直接dp的复杂度是O(n^2p)的，这样会TLE

方法一：

注意到这个dp的本质是把一个序列给分成p段，那么其中某一段会不会很长呢？

我们会发现a的增长是非常快的，而最终的答案不会很大，所以也就是说当前的i的最优转移j，不会离i太远

所以通过计算可以发现这个距离step<=40

所以时间复杂度O(40n^2)

方法二：

考虑dp优化的惯用套路

容易得出此dp是决策单调的，也就是f(i)<=f(i+1)

那么就可以决策单调优化O(nplogn)

具体的就维护一个队列，队列里每个元素存着[l,r,p]表示区间l~r，当前最优决策是p

每次从队头取出最优策略，将此次新的决策从队尾开始放入并合并区间

 1         dp[1][n]=0.0;
 2         for(int now=2;now<=number;++now)
 3         {
 4             int head=1,tail=1;
 5             q[1]={1,n-1,n};
 6             for(int i=n-1;i>=1;--i)
 7             {
 8                 while(head<tail&&q[head].l>i) ++head;
 9                 dp[now][i]=cal(now-1,i,q[head].p);
10                 while(head<tail&&cal(now-1,q[tail].r,i)<cal(now-1,q[tail].r,q[tail].p)) --tail;
11                 int position=find(now,q[tail].l,q[tail].r,i,q[tail].p);
12                 if(position)
13                 {
14                     q[tail+1]={1,position,i};
15                     q[tail].l=position+1;
16                     if(q[tail].l>q[tail].r) ++head;
17                     ++tail;
18                 }
19             }
20         }

View Code

方法三：

一个很神奇的二分套路（详见王钦石《浅析一类二分方法》）

这是一个限制段数的dp，我们把它写成不限制段数的情况

然后我们去二分一个常数C，使得式子变成这样

这里的C表示每次重新开一段所需要的代价

很明显，C越大，最优情况下分的段数就越少，C越小，最优情况下分的段数就越多

所以我们可以二分C，对于每个C，进行dp

通过n->pre[n]->pre[pre[n]]->...->1，我们可以知道存了多少次档，当存档数恰好等于p的时候，此时对应的划分方案就是读档p次时候的最优解，就是将dp的最优值减去C*p

但是有个trick，王钦石论文里也提到了

就是可能当前eps下，并没有哪个C会使得我恰好读了p次档，即某个C情况下，我读了p-1次档，在C-eps情况下，我读了p+1次档，就是没有读p次档

这时候有个结论就是C-eps时，我读p+1次档这个情况下也必定有我读p次档的解，此时原本答案是dp-(p+1)*C,现在这样改成读p次档之后，答案就是dp-p*C

这样复杂度是O(n^2logA)

当然这里的dp可以优化，但不过预处理的时候O(n^2)是跑不掉的，所以再优化也不会低于O(n^2)的复杂度

 1         int minnum=m+1;
 2         while (l+eps<=r)
 3         {
 4             long double mid=(l+r)/2;
 5             int num=check(mid);
 6             long double sum=0;
 7             for(int now=n;now!=1;now=pre[now]) sum+=w[pre[now]][now];
 8             if (num<=p)
 9             {
10                 if (num==p)
11                 {
12                     ans=sum;
13                     break;
14                 };
15                 r=mid-eps;
16             }
17             else
18             {
19                 if(num<=minnum)
20                 {
21                     ans=sum+(num-p)*mid;
22                     minnum=num;
23                 }
24                 l=mid+eps;
25             }
26         }

View Code

loj2542随机游走——最值反演+树上期望dp+fmt(代码片段)

题目：https://loj.ac/problem/2542因为走到所有点的期望就是所有点期望的最大值，所以先最值反演一下，问题变成从根走到一个点集任意一点就停止的期望值；设(f[x])，则(f[x]=fracf[fa]+1+sumlimits_vinson(f[v]+1)d[x])，其中(d[x])是(x)的度数；... 查看详情

bzoj4899记忆的轮廓题解（概率dp+决策单调性优化）(代码片段)

题目背景四次死亡轮回后，昴终于到达了贤者之塔，当代贤者夏乌拉一见到昴就上前抱住了昴“师傅！你终于回来了！你有着和师傅一样的魔女的余香，肯定是师傅”。众所周知，大贤者是嫉妒魔女沙提拉的老公，400年前... 查看详情

loj6191「美团codem复赛」配对游戏概率期望dp

...元素为1，则将这两个元素弹栈。问最终栈中元素个数的期望是多少。输入一行一个正整数n。输出一行一个实数，表示期望剩下的人数，四舍五入保留三位小数。样例输入10样例输出4.168题解概率期望dp显然任何时刻栈中的元素自... 查看详情

loj#2145.「shoi2017」分手是祝愿

题目链接LOJ#2145题解一道画风正常的……期望DP？首先考虑如何以最小步数熄灭所有灯：贪心地从大到小枚举灯，如果它亮着则修改它。可以求出总的最小步数，设为(cnt)。然后开始期望DP。设(dp[i])为当前最小步数是(i)，总最小步... 查看详情

kingxmagicspells期望dp(记忆化搜索)(代码片段)

Usedas:DivisionOne-LevelTwo:Value500SubmissionRate281/941(29.86%)SuccessRate226/281(80.43%)HighScorewatafor473.56points(6mins47secs)AverageScore323.08(for226correctsubmissions)AstheXORoperationinvolve 查看详情

考后反思（bzoj3940bzoj4899bzoj3307）(代码片段)

...没有调出来）最后骗了五分考后主要讲一下第二题：记忆的轮廓（bzoj4899）和第三题：雨天查看详情

tsp+期望——lightoj1287记忆化搜索,好题!(代码片段)

感觉是很经典的题记忆化时因为不好直接通过E判断某个状态是否已经求过，所以再加一个vis打标记即可/*E[S][u]表示从u出发当前状态是S的期望*/#include<bits/stdc++.h>usingnamespacestd;#defineN16#defineINF0x3f3f3f3fintmp[N][N],n,m;doubleE[N][1&... 查看详情

bzoj14151415:[noi2005]聪聪和可可（bfs+记忆化搜索+期望）

1415:[Noi2005]聪聪和可可TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 1640 Solved: 962DescriptionInput数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。第2行包含两个整数... 查看详情

loj#2542.「pkuwc2018」随机游走(代码片段)

...机游走，直到点集\$S\$中所有点都至少经过一次的话，期望游走几步。特别地，点\$x\$（即起点）视为一开始就被经过了一次。答案对$998 查看详情

loj10164数字游戏1(代码片段)

...[a,b][a,b]，问这个区间内有多少个不降数。数位DP的模板，记忆化搜索时枚举从当前状态开始就行。具体看注释#include<iostream>#include<cstdio&g 查看详情

loj2513治疗之雨(代码片段)

...雄加1点血，然后等概率随机k次每次对于英雄扣1点血。求期望操作几次你的英雄没血？n,m,p<=1500. 标程：1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4 查看详情

bzoj1415[noi2005]聪聪和可可期望记忆化搜索

题目描述输入数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。第2行包含两个整数C和M，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。接下来E行，每行两个整数，... 查看详情

[loj572]misakanetwork与求和[杜教筛+min25]

传送门首先g可以整除分块，然后杜教筛处理g 考虑如何用Min25筛出f，一个d有f(d)^k的贡献，当且仅当有一个>=它的质数在它前面所有的方案数就是>=它的质数个数于是Min25先处理出质数个数，然后加上合数贡献时算... 查看详情

loj2145「shoi2017」分手是祝愿

记$f_i$是从要做$i$步好操作变成要做$i-1$步好操作的期望操作次数。显然$f_i=i/n\times1+(1-i/n)\times(1+f_i+1+f_i)$，即$f_i=(n+(n-i)f_i+1)/i$。$f_n=1$。递推即可。#include<iostream>#include<cstdio>#include<vecto 查看详情

loj#2542.「pkuwc2018」随机游走（树形dp+min-max容斥）(代码片段)

...容斥设(S)为一个点的集合，每个点的权值为走到这个点的期望时间，则(Max(S))即为走遍这个集合所有点的期望时间，(Min(S))即为第一次走到这个集合的期望时间，题目所求为(Max(S))很难算于是转化为求(Min(S))设(f_u)为点从点(u)开始... 查看详情

[loj#2327]「清华集训2017」福若格斯

[LOJ#2327]「清华集训2017」福若格斯试题描述小d是4xx9小游戏高手。有一天，小d发现了一个很经典的小游戏：跳青蛙。游戏在一个(5)个格子的棋盘上进行。在游戏的一开始，最左边的两个格子上各有一个向右的青蛙，最右边的两个... 查看详情

loj3120cts2019珍珠(代码片段)

题目?$laofu$出的题?$n$个离散型随机变量$X_i$可能的值为$[1,D]$,求有至少$m$对的概率?$0\lem\le10^9?,?1\len\le10^9?,?1\leD\le10^5$题解60pts观察到能配对的个数只和颜色奇数个数有关令$L=min(D,n-2m)$，这是奇数个数上界$dp_i,j$表示前$i$... 查看详情

loj「libreojβround#4」子集

一道脑洞题，我们发现不能在一起的点对还是比较少的。我们考虑奇偶性，发现同奇偶性时一定可以，那么我们统计不可以的对，答案就是n-二分图的最大匹配。#include<bits/stdc++.h>#defineN507#defineintlonglongusingnamespacestd;intx,a[N],b[... 查看详情