题解 P2627 【[USACO11OPEN]Mowing the Lawn G】

HH_Halo · 2020-07-28 16:27:37 · 题解

Mowing the Lawn G「单调队列优化DP」

博客食用效果更佳

思路分析

• 首先不难想到，每只奶牛在当前选或者不选都有可能对后续的最佳答案产生影响，所以我们在转移时完全可以将这两个状态分开来存，即开一个二维的f数组。
• 另外像这种需要连续选物品的DP，使用前缀和数组会有奇效

• 定义f[i][0/1]数组表示到第i头牛，状态为0/1的情况，0表示不选，1表示选。那么两种状态的转移方程就可以得出：

  • 对于不选的情况，我们直接从上一个转移即可，即：f[i][0] = max(f[i-1][1],f[i-1][0])。
  • 选了的情况相对复杂，我们让当前这头牛为一连串牛的结尾，遍历起点，则有：f[i][1] = max(f[i][1],f[j-1][0]+sum[i]-sum[j-1]);

  信心满满的交上去，70分T掉

• 显然，这样的转移方程在一串牛的长度很长时时间效率会很低，所以考虑优化
• 仔细看一看f[i][1]的这个转移方程，我们是以i为终点寻找一个最优起点，那最最优的起点应该有两条性质：
  1. 效率值大
  2. 位置靠后(这样才可以形成更长的序列)
• 根据上面的性质，对于一些两个都不符合的点，显然就没有机会再选了，要想对后面的情况产生贡献，最起码得占一个，显然要用单调队列来维护，这也是单调队列的核心思想：人家比你小还比你强，凭什么选你
• 根据上面的转移方程，因为sum[i]是定值，所以用队列维护f[j-1][0]-sum[j-1]就可以了（别把前缀和丢了）

管理大大审核辛苦了qwq

Code

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 100010
#define ll long long
using namespace std;
inline ll read(){
    ll x = 0,f = 1;
    char ch =getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x * f;
}
ll n,k;
ll f[N][2],e[N],sum[N],q[N];
int main(){
    n = read(),k = read();
    for(int i = 1;i <= n;i++){
        e[i] = read();
        sum[i] = sum[i-1] + e[i];
    }
    int head = 0,tail = 1;//注意队首为0，要不你会默认最开始1不选是最优的
    q[tail] = 1;
    f[1][1] = e[1];
    for(int i = 2;i <= n;i++){
        while(head<=tail && i-q[head] > k)head++;
        f[i][1] = f[q[head]][0] + sum[i] - sum[q[head]];//既然在队首没被弹掉，肯定是最大的啦
        f[i][0] = max(f[i-1][0],f[i-1][1]);//这个直接转移就行
        while(head<=tail && f[i][0]-sum[i]>=f[q[tail]][0]-sum[q[tail]])tail--;
        q[++tail] = i;
    }
    printf("%lld\n",max(f[n][0],f[n][1]));
    return 0;
}