Luogu 2627 修建草坪 (动态规划Dp + 单调队列优化)

题意:

已知一个序列 { a [ i ] } ,求取出从中若干不大于 KK 的区间,求这些区间和的最大值。

细节:

没有细节???感觉没有???

分析:

听说有两种方法!!!

好吧实际上是等价的只是看似状态不同罢了~~~ QAQ

Round1:枚举当前点取或不取,当前点 i 取的话那么在前 KK 的数中必须要选择一个数字点 k 不取并且将 k+1i 做为新的区间,最后取最优的 k 作为转移记录下来,并且其满足最有子结构。

所以状态就是:dp[i][0/1] 表示以 i 为结尾是否取 i 最大的区间

自然转移就是:

dp [ i ][ 0 ] = max ( dp [ i-1 ][ 0 ] , dp [ i-1 ][ 1 ] )

dp [ i ][ 1 ] = max ( dp [ i ][ 1 ] , dp [ k ][ 0 ] + sum [ i ] - sum [ k ]) ( i-KK ≤ k ≤ i - 1 )

Round2:好吧还有一种思路直接考虑那个断点 k ,并且不去这个断点。

状态就变成了: f [ i ] 表示以 i 为结尾且必须取 i 的最大价值。

根据思路转移个人感觉玄学:

f [ i ] = max ( f [ i ] , f [ k -1 ] + sum [ i ] - sum [ k ] ) ( i-KK ≤ k ≤ i - 1 )

其中的 sum [ ] 都表示序列的前缀和,同上。

好吧事实总不尽人意,看一眼数据范围顿时吸一口氧气,但是无论怎样都是 T L E ,好像是废话,活活的 N × N 的算法啊。但是观察观察方程, 比如 Round 2 中的我们使用一种高级的数学方法——加法交换律!!!

就能把式子变成这个样子 —— f [ i ] = max ( f [ k -1 ] - sum [ k ] ) + sum [ i ]

这是时候你就应该大叫一声这是定区间求最值啊,然后你想怎么做都可以了吧,线段树权值、树状数组之类的 好吧我们还是正常一点还是不去惹 log n 的时间复杂万一卡常呢,最后你就会明智的选择单调队列啦啦啦啦~~~(Ps:单调递减,咳咳)

其实某些大佬闭着眼睛不用想都可以,比如 c l yy j ql c t,啦啦啦

代码的荣耀时刻:

Round1:

#include<bits/stdc++.h>
#define LL long long
#define MAXN 100010
using namespace std; LL f[MAXN], dp[MAXN][2];
int que[MAXN], n, m; int main(){
scanf("%d%d", &n, &m);
for (int i=1; i<=n; i++){
LL x;
scanf("%lld", &x);
f[i]=f[i-1]+x;
}
int tail=1, head=1;
que[1]=0;
for (int i=1; i<=n; i++) {
dp[i][0]=max(dp[i-1][1], dp[i-1][0]);
while (head<=tail && que[head]<max(0, i-m)) head++;
dp[i][1]=dp[que[head]][0]-f[que[head]]+f[i];
while (head<=tail && dp[que[tail]][0]-f[que[tail]]<=dp[i][0]-f[i]) tail--;
que[++tail]=i;
}
printf("%lld\n", max(dp[n][1], dp[n][0]));
return 0;
}
Round2:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN=100010; int n, k, que[MAXN];
LL f[MAXN], dp[MAXN]; int main(){
scanf("%d%d", &n, &k);
for (int i=1; i<=n; i++) {
LL x;
scanf("%lld", &x);
f[i]=f[i-1]+x;
}
int head=1, tail=1;
for (int i=1; i<=n; i++){
while (head<=tail && que[head]<max(i-k, 0)) ++head;
dp[i]=dp[max(que[head]-1, 0)]+f[i]-f[que[head]];
while (head<=tail && dp[max(que[tail]-1, 0)]-f[que[tail]]<=dp[i-1]-f[i]) --tail;
que[++tail]=i;
}
printf("%lld\n", dp[n]);
return 0;
}

小结:

其实小蒟蒻觉得像这种类似单调队列优化 1 D / 1 D 动态规划的情况,难在最初始状态思考以及转移,优化过程以及代码实现可以多练体进行熟练。

上一篇:HashMap 源码解读


下一篇:Java 并发编程(一) → LockSupport 详解