不看题解我不会

题意:

有k(k<=100)个人粉刷n面连续的篱笆(n<=16000)。第i人做在Si位置上,手有Li长,也只能刷Li面连续篱笆,并且必须刷第Si面。或者他可以一面也不刷。第i人每刷1面得Pi元。求最多得的钱。

思路:

如果我们用f[i][j]表示前i人刷前j面墙的最大收益,那么首先有:

1.第i人不刷:f[i][j]=max(f[i][j],f[i-1][j]);

2.第i人刷,但不刷第j面:f[i][j]=max(f[i][j],f[i][j-1]);

其次,有:

3.第i人刷第j面,且是从第k+1面刷到j面:f[i][j]=max(f[i][j],f[i-1][k]+Pi*(j-k));其中k+1<=j且k+Li>=i

所以我么可以在O(n^2k)时间内求出所有f[i][j].

但是这样对于此题还是太慢了:

注意到:如果将第三个方程变形:f[i][j]=max(f[i][j],f[i-1][k]-Pik+Pij)那么我们会发现:只要我们知道了满足条件的f[i-1][k]最大为多少,就可以准确而快速求出f[i][j]。如何这么办到呢?

方案一:

我们只需要将所有f[i-1][k]-Pik保存下来,将可选的部分取最大值就可以了。这时候我们可以利用单调队列。O(logn)转移。

方法2:

我们可以利用单调队列,维护数据位置的递增和值的递减。就可以O(1)转移。