GDKOI2016 Day1 T2 不稳定的传送门

最新推荐文章于 2023-03-13 20:17:01 发布

alan_cty

最新推荐文章于 2023-03-13 20:17:01 发布

阅读量1.4k

点赞数

分类专栏：概率与期望文章标签：概率与期望 GDKOI 不稳定的传送门

本文链接：https://blog.csdn.net/alan_cty/article/details/50804964

版权

概率与期望专栏收录该内容

18 篇文章

订阅专栏

本文介绍了一种解决T2不稳定传送门问题的方法，目标是从给定的N个点中找到从点1到点N的最小期望花费路径。每个点之间的边具有特定的使用成本和成功率，且每条边只能使用一次。文章详细解释了通过数学建模和动态规划来简化和优化路径选择的过程，最终得出最优路径的期望成本。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

T2 不稳定的传送门

给出N个点，点与点之间由单向边连接，每条边有使用的代价和成功的概率，若失败则返回出发点。每条边只能使用一次。数据保证没有环，点i与i+1之间一定有一条成功概率为100%的边，求从1走到N的最小期望花费。

神奇的概率题。设F[i]表示从i到N的最小期望，对于从i出去的确定顺序的每一条边， $F[i]=p1 * F[to1]+w1+(1-p1) * (p2 * F[to2]+w2)+(1-p1) * (1-p2) * (p3 * F[to3]+w3)....$
考虑化简这个这个式子，设 $pi*f[toi]+wi=xi,(1-pi)=yi$ ，则原式 $=x1+y1 * x2+y1 * y2 * x3+...$
对于相邻的两条边i，j。设Si表示先放i的期望，Sj表示先放j的期望，则
$Si=x1+y1 * x2+y1 * y2 * x3+...+y1 * .....* yi-1 * xi+y1 * ...* yi-1 * yi * xj$
$Sj=x1+y1 * x2+y1 * y2 * x3+...+y1 * .....* yi-1 * xj+y1 * ...* yi-1 * yj * xi$
消去相同项， $Si=xi+yi*xj,Sj=xj+yj*xi$
如果先放i比先放j更优的话，则
$xi+yi*xj < xj+yj*xi$
$yi*xj-xj < yj*xi-xi$
$(yi-1)*xj < (yj-1)*xi$
$(yi-1)/xi < (yj-1)/xj$
代入原项，得
$(1-pi-1)/(pi*f[toi]+wi)<(1-pj-1)/(pj*f[toj]+wj)$
$pi/(pi*f[toi]+wi)>pj/(pj*f[toj]+wj)$
可以证明对于不相邻的i和j，也满足这条式子。
发现等号左边只和i有关，等号右边只和j有关，于是我们可以吧这个东西排一次序，这样就得到最优顺序了。然后直接递推就好了。

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
#define M 200005
#define db double
using namespace std;
struct note{
    int x,y,c;db p,f;
}a[M];
bool cmd(note x,note y) {return x.x<y.x;}
bool cmp(note x,note y) {return x.f>y.f;}
db f[N];
int l[N],r[N],n,m;
int main() {
    scanf("%d%d",&n,&m);
    fo(i,1,n-1) scanf("%d",&a[i].c),a[i].x=i,a[i].y=i+1,a[i].p=1;
    fo(i,n,m+n-1) scanf("%d%d%lf%d",&a[i].x,&a[i].y,&a[i].p,&a[i].c);
    sort(a+1,a+m+n,cmd);
    fo(i,1,m+n-1)
        if (a[i].x!=a[i-1].x) r[a[i-1].x]=i-1,l[a[i].x]=i;
    r[a[n+m-1].x]=n+m-1;
    fd(i,n-1,1) {
        fo(j,l[i],r[i]) a[j].f=a[j].p/(a[j].p*f[a[j].y]+a[j].c);
        sort(a+l[i],a+r[i]+1,cmp);
        db x=1;
        fo(j,l[i],r[i]) {
            f[i]=f[i]+(f[a[j].y]*a[j].p+a[j].c)*x;
            x*=(1-a[j].p);
        }
    }
    printf("%.2lf",f[1]);
}