题目链接:BZOJ:http://www.lydsy.com/JudgeOnline/problem.php?id=4720 洛谷:https://www.luogu.org/problem/show?pid=1850
题意:给一张无向图,有 n 个时间,对于第 i 个时间,要去地点 c[i],每条边都有一个权值。同时,每个时间还有一个备用地址 d[i],有 m 次申请机会,通过几率为 k[i],问总消耗的期望是多少...
本题考试的时候连 floyd 都不会... 强行水了前几个点 qwq 现在一看好水,结果一发 32pts...
坑有点多,调了 1h30min 左右... 我还是太弱了 qwq 具体犯过的智障错误有:inf 开小了,inf 开大了, 数组开小了, 数组开大了等......
下面是正式题解:
首先用 floyd 预处理出两点距离 dis 备用,我们考虑怎么转移...
dp[i][j][0/1] 表示目前时间点为 i,申请了 j 次,且本次不通过/通过
式子很好想,但是需要考虑好多情况...
dp[i][j][0]=min(上次没有申请,上次申请了通过+不通过)
dp[i][j][1]=min(上次没有申请,通过通过+不通过通过+通过不通过+不通过不通过)
具体式子在代码里...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define N 2010 #define inf 1000000000 using namespace std; int n,m,v,e,c[N],d[N],dis[310][310]; double k[N],dp[N][N][2]; void pre() { for(int i=0;i<=v;i++) for(int j=0;j<=v;j++) dis[i][j]=inf; for(int i=1;i<=v;i++)dis[i][i]=0; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j][0]=dp[i][j][1]=inf; dp[1][0][0]=dp[1][1][1]=0; } void floyd() { for(int t=1;t<=v;t++) for(int i=1;i<=v;i++) for(int j=1;j<=v;j++) dis[i][j]=min(dis[i][j],dis[i][t]+dis[t][j]); } int main() { scanf("%d %d %d %d",&n,&m,&v,&e); for(int i=1;i<=n;i++)scanf("%d",&c[i]); for(int i=1;i<=n;i++)scanf("%d",&d[i]); for(int i=1;i<=n;i++)scanf("%lf",&k[i]); pre(); for(int i=1;i<=e;i++) { int a,b,w; scanf("%d %d %d",&a,&b,&w); if(a==b)continue; if(w<dis[a][b])dis[a][b]=w; dis[b][a]=dis[a][b]; } floyd(); for(int i=2;i<=n;i++) { dp[i][0][0]=dp[i-1][0][0]+dis[c[i-1]][c[i]]; for(int j=1;j<=min(m,i);j++) { dp[i][j][0]=min(dp[i-1][j][0]+dis[c[i-1]][c[i]],dp[i-1][j][1]+k[i-1]*dis[d[i-1]][c[i]]+(1.0-k[i-1])*dis[c[i-1]][c[i]]); dp[i][j][1]=min(dp[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1.0-k[i])*dis[c[i-1]][c[i]],dp[i-1][j-1][1]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+(1.0-k[i-1])*(1.0-k[i])*dis[c[i-1]][c[i]]+k[i-1]*(1.0-k[i])*dis[d[i-1]][c[i]]+(1.0-k[i-1])*k[i]*dis[c[i-1]][d[i]]); } } double ans=dp[n][0][0]; for(int i=1;i<=m;i++) {ans=min(ans,dp[n][i][0]);ans=min(ans,dp[n][i][1]);} printf("%.2lf",ans); } |
Comments | 1 条评论
orz 赵广泽大大