[算进] 换教室（期望dp）

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