算法提高课汇总

$DP$分析

集合表示 $f(i)$

• 集合: 从前$i$头牛选且没有连续$k$头牛(合法)的所有方案.

• 属性: Max

状态计算

以是否选择第$i$头牛作为划分依据.

• 不选: 集合等价于从前$i - 1$头牛选且合法的所有方案 — $f(i - 1)$.

• 选: 若选择第$i$头牛, 则包括$i$连续的一段区间长度不超过$k$. 假设区间长度为$j$, 则
  区间$i-j+1\sim i$被选择, 其区间和可以用前缀和快速计算: $s_i - s_{i-j}$; 第$i-j$
  头牛不能被选择, 剩余集合为: 从前$i-j-1$头牛选择且合法的所有方案, $f(i)$
  $=max\lbrace f(i-j-1)-s_{i-j}\rbrace +s_i$, 其中$1\le j\le k$. 若令$x=i-j$,
  则$f(i)=max\lbrace f(x-1)-s_x\rbrace+s_i, i-k\le x\le i-1$.
  设$g(x) = f(x-1)-s_x$, 则问题转变为求区间长度为$k$的$g(x)$最值, 可用单调队列优化.

综合两个子集, $f(i) = max\lbrace f(i-1), g(x)+s_i\rbrace, i-k\le x\le i-1$.

具体实现

• 边界条件: 当$i\le k$时, 其所需的子状态$g(x)$的$x$可能会小于等于0(实际操作时只会遇到$g(0)$),
  其具体含义为选择区间的长度为$j = i$, 即所有前$i$头牛均被选择, 所以$g(0)$是合法状态, 特殊判断为0.

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

typedef long long ll;

int n, m;
ll  s[N], f[N];
int q[N];

ll g(int i)
{
    if ( !i )   return 0;
    return f[i - 1] - s[i];
}

int main()
{
    cin >> n >> m;
    for ( int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        s[i] += s[i - 1];
    }

    int hh = 0, tt = -1; q[++ tt] = 0; //加入g(0) = 0
    for ( int i = 1; i <= n; i ++ )
    {
        if ( q[hh] < i - m )    hh ++;
        f[i] = max(f[i - 1], g(q[hh]) + s[i]);
        while ( hh <= tt && g(q[tt]) <= g(i) )  tt --;
        q[++ tt] = i;
    }
    cout << f[n] << endl;

    return 0;
}