Description
Solution
这题结合了DP和概率与期望，其实只要稍微知道什么是期望就可以了，
状态的构造很关键，\(F[i][j][0/1]\)表示已经到第\(i\)个课程，之前用了\(j\)个申请机会，且当前课程是(1)否(0)申请
然后就容易想到转移方程，
\(F_{i,j,0}=min\{F_{i-1,j,0}+dis(c_{i-1},c_i),F_{i-1,j,1}+dis(c_{i-1},c_i)*(1-p_{i-1})+dis(d_{i-1},c_i)*p_{i-1}\}\)
\[ F_{i,j,1}=min\{F_{i-1,j-1,0}+dis(c_{i-1},c_i)*(1-p_i)+dis(c_{i-1},d_i)*p_i, F_{i-1,j-1,1}+dis(c_{i-1},c_i)*(1-p_{i-1})*(1-p_i)+dis(d_{i-1},d_i)*p_{i-1}*p_i+ dis(c_{i-1},d_i)*(1-p_{i-1})*p_i+dis(d_{i-1},c_i)*p_{i-1}*(1-p_i) \} \]
方程看起来复杂但仔细分析会会发现其实很裸
Code
#include#include #include #define db double#define N 2010using namespace std; int n,m,V,E,c[N],d[N],g[320][320];db p[N],f[N][N][2],Ans;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*10+ch-'0';ch = getchar();} return x*f;}inline void Init(){ 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,127/2,sizeof(g)); for(int i=1;i<=E;++i){ int u=read(),v=read(),w=read(); g[u][v]=min(g[u][v],w); g[v][u]=g[u][v]; } 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=1;i<=V;++i) g[i][i]=0;}int main() { Init(); for(int i=1;i<=n;++i)for(int j=0;j<=m;++j)f[i][j][0]=f[i][j][1]=1e9; f[1][0][0]=f[1][1][1]=0; for(int i=2;i<=n;++i){ int lim=max(i,m); for(int j=0;j<=lim;++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.0-p[i-1])+g[d[i-1]][c[i]]*p[i-1]); if(j<1) continue; db tmp=f[i-1][j-1][1]+g[c[i-1]][c[i]]*(1.0-p[i-1])*(1.0-p[i])+g[d[i-1]][d[i]]*p[i-1]*p[i]; tmp+=g[c[i-1]][d[i]]*(1.0-p[i-1])*p[i]+g[d[i-1]][c[i]]*p[i-1]*(1.0-p[i]); f[i][j][1]=min(tmp,f[i-1][j-1][0]+g[c[i-1]][c[i]]*(1.0-p[i])+g[c[i-1]][d[i]]*p[i]); } } Ans=1e9; for(int i=0;i<=m;++i) Ans=min(Ans,min(f[n][i][0],f[n][i][1])); printf("%.2lf\n",Ans); return 0;}