修建草坪

修剪草坪 - LibreOJ 10177 - Virtual Judge (csgrandeur.cn)

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

然而，$FJ$ 的草坪非常脏乱，因此，$FJ$ 只能够让他的奶牛来完成这项工作。$FJ$ 有 $N$ 只排成一排的奶牛，编号为 $1$ 到 $N$。每只奶牛的效率是不同的，奶牛 i 的效率为 $E_i$

靠近的奶牛们很熟悉，如果 $FJ$ 安排超过 $K$ 只连续的奶牛，那么这些奶牛就会罢工去开派对。因此，现在 $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$。

数据范围与提示

对于全部数据，$1\le N\le 10^5,0\le E_i\le 10^9$

思路

刻意控制小聪明思绪, 思考时尽量严密

状态表示： f[i] 从1-i中选的所有方案中的最高效率 状态计算：

• 在区间$[i-k,i]$中枚举休息的奶牛 $j$, 故转移方程为：
• $dp[i]=\max \left\{dp[j-1]+{\sum }_{k=j+1}^i{E}_k\right\}(i-K\le j\le i)$
• 预处理出前缀和进行优化
• $dp[i]=\max \{dp[j-1]+\mathrm{Sum}[i]-\mathrm{Sum}[j]\}(i-K\le j\le i)$
• 然后也是把 $Sum[i]$ 移到外面
• $dp[i]=\max \{dp[j-1]-\mathrm{Sum}[j]\}+\mathrm{Sum}[i](i-K\le j\le i)$

代码

const int N = 1e5 + 10;
typedef long long LL;
LL a[N];
int q[N], hh, tt;
LL f[N];
int n, m;
 
LL g(int i)
{
    return f[max(0, i - 1)] - a[i];
}
 
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] += a[i - 1];
    }
 
    hh = 0, tt = 0;
    for (int i = 1; i <= n; i++)
    {
        while (hh <= tt && g(q[tt]) <= g(i))
            tt--;
        q[++tt] = i;
        if (hh <= tt && i - q[hh] > m)
            hh++;
        f[i] = a[i] + g(q[hh]);
    }
    cout << f[n] << endl;
    return 0;
}