题意
一天由 N个小时构成，我们称 0 点到 1 点为第 1 个小时
在第 i 个小时睡觉能够恢复 Ui 点体力。
在这个星球上住着一头牛，它每天要休息 B 个小时。
它休息的这 B 个小时不一定连续，可以分成若干段，但是在每段的第一个小时，它需要从清醒逐渐入睡，不能恢复体力，从下一个小时开始才能睡着。
另外，因为时间是连续的，即每一天的第 N 个小时和下一天的第 1 个小时是相连的（N 点等于 0 点），这头牛只需要在每 N 个小时内休息够 B 个小时就可以了。
请你帮忙给这头牛安排一个睡觉计划，使它每天恢复的体力最多。
思考
破题口在于如何找到状态表示，首先观察题目，发现制约因素仅仅知识在休息的一段时间里面，第一个小时不算，所以我们可能利用线性dp的思路，找到相邻两项的关系，这里我们用f[i][j][0&1]表示当前在第i个小时，当前以及睡了j个小时，且当前这个小时有没有睡（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
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using LL = long long;
const int N = 4000;
LL f[2][N][2], w[N];
int n, m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
memset(f,-0x3f,sizeof f);
f[1][0][0]=f[1][1][1]=0;
for(int i = 2; i <= n; i ++)
for(int j = 0; j <= min(i, m); j ++)
{
f[i & 1][j][0] = max(f[(i-1) & 1][j][1], f[(i-1) & 1][j][0]);
if(j >= 1) f[i & 1][j][1] = max(f[(i-1) & 1][j-1][1] + w[i], f[(i-1) & 1][j-1][0]);
}
LL ans = f[n & 1][m][0];
memset(f,-0x3f,sizeof f);
f[1][0][0]=0,f[1][1][1]=w[1];
for(int i = 2; i <= n; i ++)
for(int j = 0; j <= min(i, m); j ++)
{
f[i & 1][j][0] = max(f[(i-1) & 1][j][1], f[(i-1) & 1][j][0]);
if(j >= 1) f[i & 1][j][1] = max(f[(i-1) & 1][j-1][1] + w[i], f[(i-1) & 1][j-1][0]);
}
ans=max(f[n&1][m][1],ans);
cout<<ans<<endl;
return 0;
}
|
技巧总结：分类讨论
题意
在一条环形公路旁均匀地分布着 $N$ 座仓库, 编号为 $1 \sim N$, 编号为 $i$ 的仓库与编号为 $j$ 的仓库之间的距离定义为 $\operatorname{dist}(i, j)=\min (|i-j|, N-|i-j|)$, 也就是逆时针或顺时针从 $i$ 到 $j$ 中较近的一种。
每座仓库都存有货物, 其中编号为 $i$ 的仓库库存量为 $A_{i}$ 。
在 $i$ 和 $j$ 两座仓库之间运送货物需要的代价为 $A_{i}+A_{j}+\operatorname{dist}(i, j)$ 。
求在哪两座仓库之间运送货物需要的代价最大。
思考
断环为链的思想可以简述为：对于一个长度为 N 的环，我们不妨将其断开并延长一倍，使之变成一条长度为 2N 的链，并将其划分为若干部分分别考虑。
断环为链的思想可以简述为: 对于一个长度为 $N$ 的环, 我们不妨将其断开并延长一倍, 使之变成一条长度 为 $2 N$ 的链, 并将其划分为若干部分分别考虑。
首先把题面中计算代价的算式拆开, 可以得到:
在断环为链之后, 该算式等价于: 在长度为 $2 N$ 的链上, $f_{i, j}=A_{i}+A_{j}+i-j(j<i, i-j \leq N / 2)$ 。 此时, 本题已经被转化为了标准的线性 $D P$ 。
下面我们考虑如何求解该线性模型。如果按照上文推出的算式进行 $D P$, 我们需要一维枚举 $i$, 一维枚举 $j$, 总时间复杂度为 $O\left(N^{2}\right)$ 。本题中 $N \leq 10^{6}$, 这样的复杂度无法令人满意。考虑优化。
继续观察算式, 我们发现该算式可以转化为如下形态:
其中, 当 $i$ 固定时, $\left(A_{i}+i\right)$ 也确定了下来, 我们只需要考虑 $\left(A_{j}-j\right)$ 的最大值即可。
用单调队列优化。
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
| #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2000010;
int n;
int w[N];
int q[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &w[i]);
w[i + n] = w[i];
}
int res = 0;
int hh = 0, tt = -1;
int len = n / 2;
for (int i = 1; i <= n * 2; i ++ )
{
if (hh <= tt && q[hh] < i - len) hh ++ ;
res = max(res, i - q[hh] + w[q[hh]] + w[i]);
while (hh <= tt && w[q[tt]] - q[tt] <= w[i] - i) tt -- ;
q[ ++ tt] = i;
}
printf("%d\n", res);
return 0;
}
|
题意
思考
