NOIP2016换教室 题解

题目链接

一道DP题。

首先考虑怎么设计状态。

题目说总共n节课可以换m次。

我们可以用$dp[i][j]$表示第$i$节课,之前交换$j$次的期望,但是考虑到当前换和不换两种状态,我们多开一个维度,记录当前换或者不换。于是,$dp[i][j][1]$表示使用申请,$dp[i][j][0]$表示不申请。

我们令$dis_{x,y}$表示$x$教室到$y$教室的距离,$p_i$为第i节课换教室成功的概率

那么下面几种情况

  • 不交换
  • 当本次使用申请交换

然后就可以$O(n^2)$做dp了,对于$dis$,先跑一边floyd预处理出来。

注意,dis数组的初值不要太大,否则爆int。

整体难度不大,主要是看细致程度和考虑是否周全。

代码:

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>

using LL=long long;

const LL inf=0x7fffffff;

const int maxn=2e3+10;

int n,m,v,e;
int C[maxn],D[maxn];
int dis[maxn][maxn];
double K[maxn];
double dp[maxn][maxn][2];


void Floyd()
{
for(int i=1;i<=v;i++)
dis[i][i]=dis[i][0]=dis[0][i]=0;
for(int k=1;k<=v;k++)
for(int i=1;i<=v;i++)
for(int j=1;j<=v;j++)
dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]);
}

void Solve()
{
using std::min;

//注意初始状态
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
dp[i][j][0]=dp[i][j][1]=1e17;
dp[1][0][0]=dp[1][1][1]=0;

for(int i=2;i<=n;i++)
{
int cs=C[i-1],ct=C[i];
int ds=D[i-1],dt=D[i];

dp[i][0][0]=dp[i-1][0][0]+dis[cs][ct];

for(int j=1;j<=min(i,m);j++)
{
dp[i][j][0]=min(dp[i][j][0],
min(dp[i-1][j][0]
+dis[cs][ct],

dp[i-1][j][1]
+dis[ds][ct]*K[i-1]
+dis[cs][ct]*(1.0-K[i-1])));

dp[i][j][1]=min(dp[i][j][1],
min(dp[i-1][j-1][0]
+dis[cs][dt]*K[i]
+dis[cs][ct]*(1.0-K[i]),

dp[i-1][j-1][1]
+dis[cs][ct]*(1.0-K[i-1])*(1.0-K[i])
+dis[cs][dt]*(1.0-K[i-1])*K[i]
+dis[ds][ct]*K[i-1]*(1.0-K[i])
+dis[ds][dt]*K[i-1]*K[i]));
}
}
}

int main()
{
memset(dis,0x3f,sizeof dis);//别太大!

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);
for(int i=1;i<=e;i++)
{
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
dis[x][y]=dis[y][x]=std::min(dis[x][y],w);
}

Floyd();
Solve();

double ans=1e17;
for(int i=0;i<=m;i++)
ans=std::min(ans,std::min(dp[n][i][0],dp[n][i][1]));

printf("%.2lf\n",ans);
return 0;
}