我的floyd竟然写错了？今年NOIP怕不是要爆零了？
这就是一个概率dp
我们用$dp[i][j][k]$表示在第$i$个时间段，已经申请了$j$次，$k$表示本次换或不换，然后直接暴力转移
点数只有300，跑一遍floyd
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #define inf 1e17 6 using namespace std; 7 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} 8 inline int read(){ 9 #define num ch-'0' 10 char ch;bool flag=0;int res; 11 while(!isdigit(ch=getchar())) 12 (ch=='-')&&(flag=true); 13 for(res=num;isdigit(ch=getchar());res=res*10+num); 14 (flag)&&(res=-res); 15 #undef num 16 return res; 17 } 18 const int N=2005,M=305; 19 int mp[M][M],c[N][2],n,m,e,v;double dp[N][N][2],k[N],ans; 20 int main(){ 21 // freopen("testdata.in","r",stdin); 22 memset(mp,0x3f,sizeof(mp)); 23 n=read(),m=read(),v=read(),e=read(); 24 for(int i=1;i<=n;++i) c[i][0]=read(); 25 for(int i=1;i<=n;++i) c[i][1]=read(); 26 for(int i=1;i<=n;++i) scanf("%lf",&k[i]); 27 for(int i=1,u,v,w;i<=e;++i){ 28 u=read(),v=read(),w=read(); 29 cmin(mp[u][v],w),cmin(mp[v][u],w); 30 } 31 for(int i=1;i<=v;++i) mp[i][i]=mp[i][0]=mp[0][i]=0; 32 for(int k=1;k<=v;++k) for(int i=1;i<=v;++i) for(int j=1;j<=v;++j) 33 cmin(mp[i][j],mp[i][k]+mp[k][j]); 34 for(int i=0;i<=n;++i) for(int j=0;j<=m;++j) dp[i][j][0]=dp[i][j][1]=inf; 35 dp[1][0][0]=dp[1][1][1]=0; 36 for(int i=2;i<=n;++i){ 37 dp[i][0][0]=dp[i-1][0][0]+mp[c[i][0]][c[i-1][0]]; 38 for(int j=1,l=min(i,m);j<=l;++j){ 39 int c1=c[i][0],c2=c[i][1],c3=c[i-1][0],c4=c[i-1][1]; 40 cmin(dp[i][j][0],dp[i-1][j][0]+mp[c1][c3]); 41 cmin(dp[i][j][0],dp[i-1][j][1]+mp[c1][c4]*k[i-1]+mp[c1][c3]*(1-k[i-1])); 42 cmin(dp[i][j][1],dp[i-1][j-1][0]+mp[c1][c3]*(1-k[i])+mp[c2][c3]*k[i]); 43 cmin(dp[i][j][1],dp[i-1][j-1][1]+mp[c1][c3]*(1-k[i-1])*(1-k[i])+ 44 mp[c2][c3]*(1-k[i-1])*k[i]+mp[c1][c4]*k[i-1]*(1-k[i])+mp[c2][c4]*k[i-1]*k[i]); 45 } 46 } 47 ans=inf; 48 for(int i=0;i<=m;++i) cmin(ans,dp[n][i][0]),cmin(ans,dp[n][i][1]); 49 printf("%.2lf ",ans); 50 return 0; 51 }