Bzoj 4720 换教室 (期望DP)

时间：2024-07-17 21:36:50

刚发现Bzoj有Noip的题目,只会换教室这道题.....

Bzoj 题面:Bzoj 4720

Luogu题目:P1850 换教室

大概是期望DPNoip极其友好的一道题目,DP不怎么会的我想到了,大概是自己比较有成就感的题目(我才不会告诉你们,我这个题因为const int 挂了)

期望的线性性质:和的期望 = 期望的和.

期望\(E(x) = \sum_iP_i*W_i\)

那么这个题的期望就是\(L * P_i\)长度乘以概率.

知道期望的性质及期望,下面就是动态规划的部分.

设置状态:\(f[i][j][0/1]\)表示前i个教室,已经申请了j个教室,0表示这个时间段要去\(c_i\),1表示这个时间段要去\(d_i\)

之后开始想转移方程:

一. \(f[i][j][0]\)

  • 上一个教室不参加申请.
  • 上一个教室参加申请.
  • 上一个教室申请失败
  • 上一个教室申请成功

二.\(f[i][j][1]\)

  • 这个教室不参加申请
  • 这个教室申请失败
  • 这个教室申请成功
  • 这个教室参加申请
  • 这个教室申请失败

    上个教室申请成功

    上个教室申请失败
  • 这个教室申请成功

    上个教室申请成功

    上个教室申请失败
#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int maxT = 2000 + 7;

const int maxM = 90000 + 7;

const int maxN = 300 + 7;

int c[maxT],d[maxT],dis[maxN][maxN];

double k[maxT];

double E[maxT][maxT][2];

inline int read() {

    int x = 0,E = 1;char c = getchar();

    while(c < '0' || c > '9') {if(c == '-')E = -1;c = getchar();}

    while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}

    return x * E;

}

int main() {

    int 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) cin >> k[i];

    int u,g,w;

    for(int i = 1;i <= v;++ i)

        for(int j = 1;j < i;++ j)

            dis[i][j] = dis[j][i] = 999999999;

    for(int i = 1;i <= e;++ i) {

        u = read(),g = read(),w = read();

        dis[g][u] = dis[u][g] = min(dis[u][g],w);

    }

    for(int k = 1;k <= v;++ k)

        for(int i = 1;i <= v;++ i)

            for(int j = 1;j <= v;++ j)

                if(dis[i][k] + dis[k][j] < dis[i][j])

                    dis[i][j] = dis[j][i] = dis[i][k] + dis[k][j];

    for(int i = 1;i <= n;++ i)

        for(int j = 0;j <= m;++ j)

            E[i][j][0] = E[i][j][1] = 999999999;

    E[1][1][1] = E[1][0][0] = 0;

    for(int i = 2;i <= n;++ i) {

        E[i][0][0] = E[i - 1][0][0] + dis[c[i - 1]][c[i]];

        for(int j = 1;j <= min(i,m);++ j) {

            E[i][j][0] = min(E[i - 1][j][1] + k[i - 1] * dis[d[i - 1]][c[i]] + (1 - k[i - 1]) * dis[c[i - 1]][c[i]],E[i - 1][j][0] + dis[c[i - 1]][c[i]]);

           	E[i][j][1] = min(E[i - 1][j - 1][1] + k[i - 1] * k[i] * dis[d[i - 1]][d[i]] + k[i - 1] * (1 - k[i]) * dis[d[i - 1]][c[i]] + (1 - k[i - 1]) * k[i] * dis[c[i - 1]][d[i]] + (1 - k[i - 1]) * (1 - k[i]) * dis[c[i - 1]][c[i]],E[i - 1][j - 1][0] + k[i] * dis[c[i - 1]][d[i]] + (1 - k[i]) * dis[c[i - 1]][c[i]]);

        }

    }

    double minn = 9999999999;

    for(int i = 0;i <= m;++ i) minn = min(min(E[n][i][1],E[n][i][0]),minn);

    printf("%.2lf\n", minn);

    return 0;

}

相关文章