P2627 [USACO11OPEN] Mowing the Lawn G 学习笔记

a_little_carrot · 2024-11-26 22:01:07 · 个人记录

problem

/*
很明显的dp
我们设 f[i, j] 为第 i 头牛在 j 状态时（0不选 1选）最大贡献
此时对于 f[i, 1]，取 max(f[j, 0] + pre[i] - pre[j]) (j∈[i - k, i])
然而会TLE一个点（数据还是水）
注意到 max(f[j, 0] + pre[i] - pre[j]) => max(f[j, 0] - pre[j]) + pre[i]
于是我们需要一个单调队列，维护 max(f[j, 0] - pre[j])
最终时间复杂度 O(n * 4 + n)，抛开常数不谈，O(n)
*/
#include "bits/stdc++.h"
#define For(i, l, r) for(int i = (l) ; i <= (r) ; ++i)
typedef long long ll ;
using namespace std ;
const int N = 100005 ;
ll n, k, f[N][2], a[N], pre[N] ;
int q[N], l, r ;
int main()
{
    ios::sync_with_stdio(false) ;
    cin.tie(0) ; cout.tie(0) ;
    cin >> n >> k ;
    For(i, 1, n)
    {
        cin >> a[i] ;
        pre[i] = pre[i - 1] + a[i] ;
    }
    For(i, 1, n)
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][1]) ;
        while(q[l] < i - k && l <= r) l++ ;
        f[i][1] = f[q[l]][0] - pre[q[l]] + pre[i] ;
        while(f[i][0] - pre[i] > f[q[r]][0] - pre[q[r]] && l <= r) r-- ;
        q[++r] = i ;
    }
    cout << max(f[n][0], f[n][1]) ;
    return 0 ;
}