Luogu P1850 [NOIp2016提高组]换教室 | 期望dp

题目链接

思路:
<1>概率与期望
期望=情况①的值*情况①的概率+情况②的值*情况②的概率+……+情况n的值*情况n的概率
举个例子,抛一个骰子,每一面朝上的概率都是1/6,则这一个骰子落地后朝上的那一面的期望值就为:1*1/6+2*1/6+3*1/6+4*1/6+5*1/6+6*1/6=21/6=3.5 你们懂的(其实是我不怎么会) <2>floyd 你们懂的(这一个我是会的) <3>期望dp dp[i][j][0]表示在前i个时间段,申请换了j个教室,第i个时间段不申请换教室时的最优解 dp[i][j][1]表示在前i个时间段,申请换了j个教室,第i个时间段申请换教室时的最优解 对于第x次申请,失败的概率为(1-k[x]),成功的概率即为k[x] 对于dp[i][j][0]可以由三种情况转移过来: 1.上一个时间段不申请 2.上一个时间段申请失败 3.上一个时间段申请成功 其中,第2、3种属于同一类 对于dp[i][j][1]可以由六种情况转移过来: 1.上一个时间段不申请,这一个时间段申请失败 2.上一个时间段不申请,这一个时间段申请成功 3.上一个时间段申请失败,这一个时间段申请失败 4.上一个时间段申请失败,这一个时间段申请成功 5.上一个时间段申请成功,这一个时间段申请失败 6.上一个时间段申请成功,这一个时间段申请成功 其中,第1、2种属于同一类,第3、4、5、6种属于同一类。 对于每一种情况,都将所属这一种情况的每一个操作的概率相乘,即可求出这一种情况出现的概率,再乘以相应两个课室之间的最短路径,就可以得出期望值。最后dp[n][1..m][0..1]中的最小值就是答案。 <4>反思 这道题的转移方程很长,然而我一开始并没有换行,然后就有了一个我看不出的错误,然后我提交上去就WA了,然后我冥思苦想一行一行对照题解,然后我还是没能找出错误,然后llx来了叫我对拍,然后我就开始对拍了,然后我就发现了错误,原来是一个地方忘了减一,然后我提交上去就A了,然后就没有然后了…… <完>
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<string>
#include<sstream>
#include<cstring>
    using namespace std;
    const int INF=10000000;
    int c[2005],d[2005],f[305][305];
    double k[2005],dp[2005][2005][2];
int main()
{
    int n=0,m=0,v=0,e=0;
    double ans=INF;
    scanf("%d%d%d%d",&n,&m,&v,&e);
    if(n==1) { printf("0.00");    return 0; }
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    for(int i=1;i<=n;i++) scanf("%lf",&k[i]);
    for(int i=1;i<=v;i++)//初始化邻接矩阵 
        for(int j=1;j<i;j++)
            f[i][j]=f[j][i]=INF;
    for(int i=1;i<=e;i++)
    {
        int a=0,b=0,w=0;
        scanf("%d%d%d",&a,&b,&w);
        f[a][b]=f[b][a]=min(f[a][b],w);//存边 
    }
    for(int T=1;T<=v;T++)//floyd 
        for(int i=1;i<=v;i++)
            for(int j=1;j<i;j++)
                f[i][j]=f[j][i]=min(f[i][j],f[i][T]+f[T][j]);
    for(int i=1;i<=n;i++)//dp数组初始化 
        for(int j=0;j<=m;j++)
            dp[i][j][0]=dp[i][j][1]=INF;
    dp[1][0][0]=dp[1][1][1]=0;//边界条件 
    for(int i=2;i<=n;i++)//dp 
        for(int j=0;j<=min(m,i);j++)
        {    
            if(j>0) dp[i][j][1]=min(dp[i-1][j-1][0]+f[c[i-1]][c[i]]*(1-k[i])+f[c[i-1]][d[i]]*k[i],
                                    dp[i-1][j-1][1]+f[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+
                                                    f[c[i-1]][d[i]]*(1-k[i-1])*k[i]+
                                                    f[d[i-1]][c[i]]*k[i-1]*(1-k[i])+
                                                    f[d[i-1]][d[i]]*k[i-1]*k[i]);            
            dp[i][j][0]=min(dp[i-1][j][0]+f[c[i-1]][c[i]],
                            dp[i-1][j][1]+f[c[i-1]][c[i]]*(1-k[i-1])+
                                          f[d[i-1]][c[i]]*k[i-1]);    
            if(i==n) ans=min(ans,min(dp[i][j][0],dp[i][j][1]));//维护最小期望值 
        }
    printf("%.2lf",ans);//四舍五入精确到小数点后2位,输出 
    return 0;
}
原文地址:https://www.cnblogs.com/wozaixuexi/p/8456147.html