修剪草坪 (mowlawn. cpp/c/pas)

题目描述

在一年前赢得了小镇的最佳草坪比赛后, FJ 变得很懒, 再也没有修剪过草坪. 现在, 新一轮的最佳草坪比赛又开始了, FJ 希望能够再次夺冠.

然而, FJ 的草坪非常脏乱, 因此, FJ 只能够让他的奶牛来完成这项工作. FJ 有 \(N (1 \leq N \leq 100,000)\) 只排成一排的奶牛, 编号为 1...... N. 每只奶牛的效率是不同的, 奶牛 i 的效率为 \(E_i (0 \leq E_i \leq 10^9)\).

靠近的奶牛们很熟悉, 因此, 如果 FJ 安排超过 \(K (1 \leq K \leq N)\) 只连续的奶牛, 那么, 这些奶牛就会罢工去开派对:) . 因此, 现在 FJ 需要你的帮助, 计算 FJ 可以得到的最大效 率, 并且该方案中没有连续的超过 K 只奶牛.

输入格式

第一行: 空格隔开的两个整数 N 和 K

第二到 N+1 行: 第 i+1 行有一个整数 E_i

输出格式

第一行: 一个值, 表示 FJ 可以得到的最大的效率值.

样例输入

5 2
1
2
3
4
5

样例输出

12

输入解释

FJ 有 5 只奶牛, 他们的效率为 1, 2, 3, 4, 5. 他们希望选取效率总和最大的奶牛, 但是 他不能选取超过 2 只连续的奶牛

FJ 可以选择除了第三只以外的其他奶牛, 总的效率为 1+2+4+5=12.

Explanation

似乎直接 DP 带一下优化就可以过差不多一半的分了.

更高的解请自行参见 hzwer 的源代码或 Google USACO.

40 分解法:


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 100100;

int n, K;
lli E[maxn], sum_d[maxn], dp[maxn];
#define sum(_l,_r) (sum_d[_r]-sum_d[(_l)-1])

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &E[i]);
    for (int i = 1; i <= n; i++)
        sum_d[i] = sum_d[i - 1] + E[i];
    dp[1] = E[1];
    for (int i = 2; i <= n; i++) {
        if (i <= K)
            dp[i] = sum(1, i);
        for (int j = max(0, i - K - 1); j <= n - 1; j++)
            dp[i] = max(dp[i], dp[j] + sum(j + 2, i));
    }
    printf("%lld\n", dp[n]);
    return 0;
}

Source Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ll long long
#define linf 99999999999999LL
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,K,l,r;
ll ans,mn=linf,f[100005];
int e[100005];
struct data{int num;ll v;}q[100005];
int main()
{
    freopen("mowlawn.in","r",stdin);
    freopen("mowlawn.out","w",stdout);
    n=read();K=read();
    for(int i=1;i<=n;i++)
        e[i]=read(),ans+=e[i];
    for(int i=1;i<=n;i++)
    {
        f[i]=e[i]+q[l].v;
        while(q[r].v>f[i]&&l<=r)r--;
        q[++r].v=f[i];
        q[r].num=i;
        while(q[l].num<i-K)l++;
    }
    for(int i=n-K;i<=n;i++)
        mn=min(mn,f[i]);
    printf("%I64d",ans-mn);
    return 0;
}