翻车笔记_ Noip2016Day1T3 换教室 [Floyd, 期望DP]

期望与现实总是背道而驰

懵逼的 题目

传送至 UOJ

扯淡的 题解

一开始设的状态比较鬼畜然后发现不会转移了…
一开始设的f[i][j][0 / 1]代表在 i 时间段, 已经用了 j 次交换, 0 代表在 c 教室, 1 代表在 d 教室, 的最小期望
然后…发现就玩不转了…样例还能过差评
因为不能知道当前的申请能否通过
然后就扔了…
今天翻到menci的blog发现这道题的题解…才不是抄题解呐
Menci的题解(无限敬仰Orz)
发现状态可以表示成: 0 代表没有申请, 1 代表申请了的最小期望
然后就可以转移了…

沙茶的 代码

突然发现我没四舍五入也过了 辣鸡数据

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAXN (300 + 5)
#define MAXM (90000 + 5)
#define MAXT (2000 + 5)
#define MAXC (2000 + 5)
#define INF (0x7ffffff)
#define DD double
using namespace std;
int n, m;
int dis[MAXN][MAXN];
int ti, ch;
int c[MAXT];
int d[MAXT];
DD k[MAXT];
DD f[MAXT][MAXT][2];// f[i][j][0 / 1]: 当前在 i 时间段, 已经申请了 j 次, [0 / 1]: 当前是否申请
DD ans = INF;

void init();
void floyd();
void dp();
int main()
{
init();
floyd();
dp();
printf("%.2lf", ans);
return 0;
}

void init()
{
memset(dis, 0x7f, sizeof(dis));
memset(f, 0x7f,sizeof(f));
scanf("%d%d%d%d", &ti, &ch, &n, &m);
for (int i = 1; i <= ti; i++)
{
scanf("%d", &c[i]);
}
for (int i = 1; i <= ti; i++)
{
scanf("%d", &d[i]);
}
for (int i = 1; i <= ti; i++)
{
scanf("%lf", &k[i]);
}
int srx, sry, srz;
for (int i = 1; i <= n; i++)
{
dis[i][i] = 0;
}
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &srx, &sry, &srz);
dis[sry][srx] = dis[srx][sry] = min(dis[srx][sry], srz);
}
}

void floyd()
{
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i != j && j != k && k != i && dis[i][k] < INF && dis[k][j] < INF)
{
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
}

void dp()
{
f[1][0][0] = 0;
f[1][1][1] = 0;
c[0] = d[0] = 0;
dis[0][c[0]] = dis[0][c[1]] = dis[0][d[0]] = dis[0][d[1]] = 0;
for (int i = 2; i <= ti; i++)
{
f[i][0][0] = f[i - 1][0][0] + dis[c[i - 1]][c[i]];
f[i][0][1] = INF;
for (int j = 1; j <= min(ch, i); j++)
{
f[i][j][0] = min(f[i][j][0], f[i - 1][j][0] + dis[c[i - 1]][c[i]]);
f[i][j][0] = min(f[i][j][0], f[i - 1][j][1] + (dis[d[i - 1]][c[i]] * k[i - 1]) + (dis[c[i - 1]][c[i]] * (1 - k[i - 1])));
f[i][j][1] = min(f[i][j][1], f[i - 1][j - 1][0] + (k[i] * dis[c[i - 1]][d[i]]) + ((1 - k[i]) * dis[c[i - 1]][c[i]]));
f[i][j][1] = min(f[i][j][1], f[i - 1][j - 1][1] + (k[i] * k[i - 1] * dis[d[i - 1]][d[i]]) + ((1 - k[i - 1]) * k[i] * dis[c[i - 1]][d[i]]) + (k[i - 1] * (1 - k[i]) * dis[d[i - 1]][c[i]]) + ((1 - k[i - 1]) * (1 - k[i]) * dis[c[i - 1]][c[i]]));
// if (f[i][j][0] < INF)
// printf("%d %d %d: %.2lf\n", i, j, 0, f[i][j][0]);
// if (f[i][j][1] < INF)
// printf("%d %d %d: %.2lf\n", i, j, 1, f[i][j][1]);
}
}
for (int i = 0; i <= ch; i++)
{
ans = min(ans, f[ti][min(i, ti - 1)][0]);
ans = min(ans, f[ti][min(i, ti)][1]);
}
}
/*
3 2 3 3
2 1 2
1 2 1
0.8 0.2 0.5
1 2 5
1 3 3
2 3 1
*/

By 脑子抽风的 Cansult