BZOJ 2442 [Usaco2011 Open]修剪草坪

BZOJ_2442

    这个题目可以用f[i]表示递推到第i个点时得到的最优解。不妨设A[]表示前缀和，那么当前有两种决策，要么不选当前这个点，要么一并向前选择若干个点，这样可以得到状态转移方程f[i]=max{f[j]+A[i]-A[j+1](i-K-1<=j<=i-2),f[i-1]}。

    如果裸着做的话是O(N^2)的，但是对状态转移方程中f[j]+A[i]-A[j+1]变形之后就会得到f[j]-A[j+1]+A[i]，这样如果我们用单调队列维护f[j]-A[j+1]的最大值就可以做到O(1)决策了。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXD 100010
typedef long long LL;
int N, K;
LL a[MAXD], f[MAXD];
struct St
{
    int id;
    LL f;
    St(){}
    St(int _id, LL _f) : id(_id), f(_f){}
}q[MAXD];
void init()
{
    int i;
    for(i = 1, a[0] = 0; i <= N; i ++) scanf("%lld", &a[i]), a[i] += a[i - 1];
}
void solve()
{
    int i, front, rear;
    LL ans = 0;
    front = rear = f[0] = 0;
    q[rear ++] = St(-1, 0);
    for(i = 1; i <= N; i ++)
    {
        if(i >= 2)
        {
            while(front < rear && q[rear - 1].f < f[i - 2] - a[i - 1]) -- rear;
            q[rear ++] = St(i - 2, f[i - 2] - a[i - 1]);
        }
        while(front < rear && q[front].id < i - K - 1) ++ front;
        f[i] = std::max(a[i] + q[front].f, f[i - 1]);
    }
    printf("%lld\n", f[N]);
}
int main()
{
    while(scanf("%d%d", &N, &K) == 2)
    {
        init();
        solve();
    }
    return 0;
}
/*
Sample Input:

4 1
10
1
2
10

Sample Output:

20

*/