水题笔记_ luogu1594 护卫队 [序列DP, long long]wwww

卡最大值的人都应该%^#%#%^

懵逼的 题目

传送至 Luogu

扯淡的 题解

本来想写ST表…
大失败
后来想n^2求最大值还不是稳稳30min A(flag)?
大失败
后来发现精度有问题 心想改完了怕不是能A(flag)?
大失败
看看讨论发现INF要设成9223372036854775807ll(MAXLL)
终于….
思路挺简单, 见第一行的注释

沙茶的 代码

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
// f[i] 前i辆车最小的通过时间
// f[i] = min(f[i], f[j] + st[i][j]) (j < i);

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define MAXN (2000 + 5)
#define MAXL (10 + 5)
#define INF (9223372036854775807ll)
#define DD double
#define LL long long
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
struct car
{
LL weight;
DD time;
}a[MAXN];
LL n;
LL lgn;
LL bw, bl;
LL fr[MAXN];
DD st[MAXN][MAXN];//max time;
DD f[MAXN];
DD ans;
DD stmax(int, int);
void initst();
void dp();
int main()
{
scanf("%lld%lld%lld", &bw, &bl, &n);
LL srspeed;
fr[0] = 0;
for (int i = 1; i <= n; i++)
{
scanf("%lld%lld", &a[i].weight, &srspeed);
a[i].time = (DD) (bl * 60) / srspeed;
fr[i] = fr[i - 1] + a[i].weight;
}
initst();
/*for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n ; j++)
{
printf("%.2lf ", st[i][j]);
}
puts("");
}*/
dp();
printf("%0.1lf", ans);
return 0;
}
void initst()
{
a[0].time = 0;
for (int i = 0; i <= n; i++)
{
st[i][i] = a[i].time;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= (n - i); j++)
{
st[j][j + i] = max(a[j + i].time, st[j][j + i - 1]);
}
}
}
DD stmax(int from, int to)
{
return st[from][to];
}
void dp()
{
for (int i = 1; i <= n; i++)
{
f[i] = INF;
for (int j = 0; j < i; j++)
{
if (((LL)fr[i] - fr[j]) <= bw)
{
f[i] = min(f[i], f[j] + stmax(j + 1, i));
}
}
}
f[n] *= 10;
ans = floor(f[n] + 0.5);
ans /= 10;
}
/*
100 5 10
40 25
50 20
50 20
70 10
12 50
9 70
49 30
38 25
27 50
19 70
*/

By 作业写不完把老师都惹炸毛的 Cansult