P1850 [NOIP2016 提高组] 换教室 【期望dp】

状态表示很重要！
dp[i][j][0]: 上完i节使用了j次申请，本节课没有申请的走过路程的期望
dp[i][j][1]: 上完i节使用了j次申请，本节课使用申请的走过路程的期望
转移方程直接看代码，太多了

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <iostream>
#include <map>

#define go(i, l, r) for(int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define god(i, r, l) for(int i = (r), i##end = (int)(l); i >= i##end; --i)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 2e3+10;
const ll maxM = 1e6+10;
const ll inf_int = 1e8;
const ll inf_ll = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

void pt(){ cout<<'\n';}
template<class H, class ... T> void pt(H h,T... t){ cout<<" "<<h; pt(t...);}

//--------------------------------------------
int N,M,V,E;
int a1[maxn],a2[maxn];
double p[maxn];
double Ept[2][maxn][maxn];
int G[305][305];
double dp[2020][2020][2];
//dp[i][j][0]: 上完i节使用了j次申请，本节课没有申请的走过路程的期望
//dp[i][j][1]: 上完i节使用了j次申请，本节课使用申请的走过路程的期望
void floyd(){
    go(k,1,V) go(i,1,V) go(j,1,V) G[i][j] = min(G[i][j],G[i][k] + G[k][j]);
}
void solve(){
    go(i,0,2000) go(j,0,2000) go(k,0,1) dp[i][j][k] = 1e18;
    dp[1][0][0] = 0;
    dp[1][1][1] = 0;
    for(int i = 2;i<=N;i++){
        int c1 = a1[i-1],c2 = a1[i];
        int d1 = a2[i-1],d2 = a2[i];
        for(int j = 0;j<=min(i,M);j++){
            double ans1 = dp[i-1][j][0] + G[c1][c2];
            double ans2 = dp[i-1][j][1] + p[i-1] * G[d1][c2] + (1-p[i-1]) * G[c1][c2];
            dp[i][j][0] = min(ans1,ans2);

            if(j > 0){
                double ans3 = dp[i-1][j-1][0] + p[i] * G[c1][d2] + (1-p[i]) * G[c1][c2];
                double ans4 = dp[i-1][j-1][1] + p[i-1] * p[i] * G[d1][d2] + p[i-1] * (1-p[i]) * G[d1][c2] +\
                              (1-p[i-1])*p[i]*G[c1][d2] + (1-p[i-1])*(1-p[i]) * G[c1][c2];
                dp[i][j][1] = min(ans3,ans4);
            }
        }
    }
    double ans = 1e18;
    for(int j = 0;j<=M;j++){
        ans = min(ans,dp[N][j][0]);
        ans = min(ans,dp[N][j][1]);
    }
    printf("%.2lf\n",ans);
}
int main() {
//    debug_in;
//    debug_out;


    read(N,M,V,E);
    go(i,1,N) read(a1[i]);
    go(i,1,N) read(a2[i]);
    go(i,1,N) scanf("%lf",&p[i]);
    go(i,1,V) go(j,1,V) if(i != j) G[i][j] = inf_int;
    go(i,1,E){
        int x,y,z;read(x,y,z);
        if(x == y) continue;
        G[x][y] = min(G[x][y],z);
        G[y][x] = min(G[y][x],z);
    }

    floyd();
    solve();

    return 0;
}