#機率、數學期望，動态規劃#洛谷 1850 換教室

題目

分析

設 d p [ n ] [ m ] [ 0 / 1 ] dp[n][m][0/1] dp[n][m][0/1]表示前 n n n個時間段共申請 m m m次時該時間段申不申請換教室的最短路徑，方程顯然

代碼

#include <cstdio>
#include <cctype>
#include <cstring>
#define rr register
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
int n,m,nn,t,now[2001],tur[2001],dis[301][301];
double  k[2001],dp[2][2001][2];
inline signed iut(){
     rr int ans=0; rr char c=getchar();
     while (!isdigit(c)) c=getchar();
     while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
     return ans;                        
}
signed main(){
    n=iut (); m=iut(); nn=iut(); t=iut();
    memset(dis,127/3,sizeof(dis));
    for (rr int i=1;i<=n;++i) now[i]=iut();
    for (rr int i=1;i<=n;++i) tur[i]=iut();
    for (rr int i=1;i<=n;++i) scanf("%lf",&k[i]);
    for (;t;--t){
        rr int x=iut(),y=iut(),w=iut();
        dis[x][y]=dis[y][x]=min(dis[x][y],w);
    }
    for (rr int k=1;k<=nn;++k)
    for (rr int i=1;i<=nn;++i)
    for (rr int j=1;j<=nn;++j) if (i!=j&&i!=k&&j!=k)
        dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    for (rr int i=1;i<=nn;++i)
        dis[i][0]=dis[0][i]=dis[i][i]=0;
    for (rr int i=0;i<=m;++i) dp[1][i][0]=dp[1][i][1]=dis[0][0];
    dp[1][0][0]=dp[1][1][1]=0;
    for (rr int i=2;i<=n;++i){
        for (rr int j=0;j<=m;++j) dp[i&1][j][0]=dp[i&1][j][1]=dis[0][0];
        rr int tt=min(i,m); dp[i&1][0][0]=dp[(i&1)^1][0][0]+dis[now[i-1]][now[i]];
        for (rr int j=1;j<=tt;++j){
            dp[i&1][j][0]=min(dp[(i&1)^1][j][0]+dis[now[i-1]][now[i]],dp[(i&1)^1][j][1]+k[i-1]*dis[tur[i-1]][now[i]]+(1-k[i-1])*dis[now[i-1]][now[i]]);
            dp[i&1][j][1]=min(dp[(i&1)^1][j-1][0]+dis[now[i-1]][tur[i]]*k[i]+dis[now[i-1]][now[i]]*(1-k[i]),dp[(i&1)^1][j-1][1]+k[i-1]*k[i]*dis[tur[i-1]][tur[i]]+k[i-1]*(1-k[i])*dis[tur[i-1]][now[i]]+(1-k[i-1])*k[i]*dis[now[i-1]][tur[i]]+(1-k[i-1])*(1-k[i])*dis[now[i-1]][now[i]]);
        }
    }
    rr double ans=1e18;
    for (rr int i=0;i<=m;++i)
        ans=min(ans,min(dp[n&1][i][0],dp[n&1][i][1]));
    return !printf("%.2lf",ans);
}