「NOIP2016」换教室

发布于 2018-08-17  355 次阅读


这道题甚至不如 T2 难...放在 T3 真的合适吗...

题目链接

题目描述

一张无向带权图,需要选择 $ N $ 次。每次在两个点 $ c_i,d_i $ 中,有 $ p_i $ 的概率选择点 $ d_i $,有 $ 1-p_i $ 的概率选择点 $ c_i $ ,每次选择相互独立。至多能选 $ M $ 次 $ d $ 类节点现在求出所有选择的路线方案中的最小期望值。

解题报告

~~看到期望了直接弃疗~~

这一题考的是期望的基本知识,所以大可不用弃疗。

~~感觉就是出题人为了强行增加难度套了个期望?~~

对于期望计算就是事件价值/代价 $*$ 概率,对其求和。

这样我们首先发现点非常的少,Floyd 处理最短路。

然后我们考虑动态规划。设 $ f[i][j][1/0] $ 表示考虑到第 $i$ 次选择,已经选择了 $j$ 次 $d$ 类节点,这一次是否选 $d$ 类节点的最小期望值。

显然转移方程如下:

设 $ dis[i][j] $ 表示 i 到 j 的最短路,$ c[i],d[i],p[i] $ 如题目所述。

dp转移代码如下(公式太长了写不开)

c++
f[i][j][0] = std::min(f[i-1][j][0]+map[c[i-1]][c[i]],f[i-1][j][1] + p[i-1] * map[d[i-1]][c[i]] + map[c[i-1]][c[i]] * (1.0-p[i-1]));
f[i][j][1] = std::min(f[i-1][j-1][0] + map[c[i-1]][d[i]]*p[i] + map[c[i-1]][c[i]]*(1-p[i]),f[i-1][j-1][1] + map[c[i-1]][c[i]] * (1-p[i-1])*(1-p[i]) + map[c[i-1]][d[i]] * (1-p[i-1])*p[i] + map[d[i-1]][c[i]] * p[i-1]*(1-p[i]) + map[d[i-1]][d[i]] * p[i-1] * p[i]);

这个方程的细节很多,还请读者自己体会。

其实就是加上所有的期望。

样例代码

#include 
#include 
#include 
#include 

const int MAXN = 2000 + 5;

double p[MAXN],map[MAXN][MAXN],f[MAXN][MAXN][2];
int c[MAXN],d[MAXN];
int N,M,v,e;

inline void Read(){
    scanf("%d%d%d%d",&N,&M,&v,&e);
    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",p+i);
    for(int i = 1;i <= v;i++)
        for(int j = 1;j <= v;j++)
            map[i][j] = (double)INT_MAX;
    for(int i = 1;i <= v;i++)
        map[i][i] = 0;
    double w;
    for(int u,v,i = 1;i <= e;i++){
        scanf("%d%d%lf",&u,&v,&w);
        map[u][v] = map[v][u] = std::min(w,map[u][v]);
    }
}

inline void Floyd(){
    for(int k = 1;k <= v;k++)
        for(int i = 1;i <= v;i++)
            for(int j = 1;j <= v;j++)
                map[i][j] = std::min(map[i][j],map[i][k] + map[k][j]);
}

inline void dp(){
    for(int i = 1;i <= N;i++)
        for(int j = 0;j <= M;j++)
            f[i][j][0] = f[i][j][1] = (double)INT_MAX;
    f[1][0][0] = f[1][1][1] = 0.0;
    for(int i = 2;i <= N;i++){ //f[i][j][k]->时刻 i,更换 j。
        for(int j = 0;j <= M;j++){
            f[i][j][0] = std::min(f[i-1][j][0]+map[c[i-1]][c[i]],f[i-1][j][1] + p[i-1] * map[d[i-1]][c[i]] + map[c[i-1]][c[i]] * (1.0-p[i-1]));
            if(j){
                f[i][j][1] = std::min(f[i-1][j-1][0] + map[c[i-1]][d[i]]*p[i] + map[c[i-1]][c[i]]*(1-p[i]),f[i-1][j-1][1] + map[c[i-1]][c[i]] * (1-p[i-1])*(1-p[i]) + map[c[i-1]][d[i]] * (1-p[i-1])*p[i] + map[d[i-1]][c[i]] * p[i-1]*(1-p[i]) + map[d[i-1]][d[i]] * p[i-1] * p[i]);
            }
        }
    }
    double ans = (double)INT_MAX;
    for(int i = 0;i <= M;i++)
        ans = std::min(ans,std::min(f[N][i][0],f[N][i][1]));
    printf("%.2f\n",ans);
}

int main(){
    Read();
    Floyd();
    dp();
    return 0;
}


一个OIer。