首页 > 其他 > 详细

[算进] 换教室(期望dp)

时间:2020-03-06 15:12:26      阅读:42      评论:0      收藏:0      [点我收藏+]

Problem

ACwing 题目地址

洛谷 题目地址

Solution

特水的一道题,但是联赛前是半抄题解过的,今天再做一遍。

决策特别明显:第 i 节课申请换教室或者不申请换教室

根据期望的定义:不申请,则期望消费就是上一个教室到这一个教室的路程(如果上一次申请的话,上一次的教室就有两种可能,就要乘上相应的概率);申请,则期望消费就是上一个教室到这一个教室的路程再乘上相应的概率(同理要分别讨论上一次是否申请,同理乘上相应概率)(这里便是这个题目复杂的地方)

我们可以根据决策推导出需要设计的状态:\(f[i][j][0/1]\) 表示前 \(i\) 次申请了 \(j\) 次,这次否/是选择申请(0是没有申请、1是申请了)。

例如 \(f[i][j][0]\) 的转移需要分类讨论上一次是否申请,从中选取最小值:

  • 上一次没有申请:\(f[i-1][j][0]+g[c_{i-1}][c_i]\)

  • 上一次有申请:\(f[i-1][j][1]+g[c_{i-1}][c_i]*(1-p_{i-1})+g[d_{i-1}][c_i]*p_{i-1}\)

\(g[i][j]\) 表示 \(i\)\(j\) 的距离,\(p_i\) 表示第 \(i\) 次申请成功的概率)

\(f[i][j][1]\) 的转移也是同理的,只是略显麻烦一点。(要多考虑一层,当前是哪个教室乘上相应概率)

距离的预处理用 \(Floyd\)

值得注意的是,double 类型的数组清空最好不用 memset

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
#define INF 99999999
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int V_N = 307, N = 2007;
int n,m,V,E;
int g[V_N][V_N];
int c[N],d[N];
double p[N],f[N][N][2];
void Floyd() {
    for(int k=1;k<=V;++k)
        for(int i=1;i<=V;++i)
            for(int j=1;j<=V;++j)
                g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
    for(int i=0;i<=V;++i) g[0][i] = g[i][0] = g[i][i] = 0;
    /*puts("test dist");
    for(int i=0;i<=V;++i)
        for(int j=0;j<=V;++j)
            printf("%d->%d dist=%d\n",i,j,g[i][j]);
    puts("test end.\n");*/
}
int main()
{
    n = read(), m = read(), V = read(), E = read();
    for(int i=1;i<=n;++i) c[i] = read();
    for(int i=1;i<=n;++i) d[i] = read();
    for(int i=1;i<=n;++i) scanf("%lf",&p[i]);
    memset(g, 0x3f, sizeof(g));
    for(int i=1,u,v,w;i<=E;++i) {
        u = read(), v = read(), w = read();
        g[u][v] = g[v][u] = min(g[u][v],w);
    }
    Floyd();
    for(int i=1;i<=n;++i)
        for(int j=0;j<=m;++j)
            f[i][j][0] = f[i][j][1] = INF;
    f[1][0][0] = f[1][1][1] = 0;
    for(int i=2;i<=n;++i)
        for(int j=0;j<=m;++j) {
            f[i][j][0] = min(f[i-1][j][0]+g[c[i-1]][c[i]], f[i-1][j][1]+g[c[i-1]][c[i]]*(1-p[i-1])+g[d[i-1]][c[i]]*p[i-1]);
            if(j == 0) continue;
            f[i][j][1] = min(f[i-1][j-1][0]+g[c[i-1]][c[i]]*(1-p[i])+g[c[i-1]][d[i]]*p[i],
                             f[i-1][j-1][1]+g[c[i-1]][c[i]]*(1-p[i-1])*(1-p[i])
                                           +g[c[i-1]][d[i]]*(1-p[i-1])*p[i]
                                           +g[d[i-1]][c[i]]*p[i-1]*(1-p[i])
                                           +g[d[i-1]][d[i]]*p[i-1]*p[i]);
        }
    double ans = INF;
    for(int i=0;i<=m;++i) {
        ans = min(ans, min(f[n][i][0], f[n][i][1]));
        //printf("test: %.2lf %.2lf\n",f[n][i][0],f[n][i][1]);
    }
    printf("%.2lf\n",ans);
    return 0;
}    

Summary

double 数组清空这里不要用 memset(f, 0x3f, sizeof(f)) !!!而是改用下列代码:

for(int i=1;i<=n;++i)
    for(int j=0;j<=m;++j)
        f[i][j][0] = f[i][j][1] = INF;

两行泪、两行泪。

[算进] 换教室(期望dp)

原文:https://www.cnblogs.com/BaseAI/p/12426500.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!