传送门:>Here<
题意:不能有连续超过$k$个奶牛的一段,求最大的和
思路分析
Dp还是容易看出来的。
我的第一感觉是一维,$f[i]$表示前i头奶牛的最大效率。其实这也是可以解的,具体方法将会在后文介绍。
考虑二维的解法,$f[i][0]$表示奶牛i不参与时的最大效率,$f[i][1]$表示奶牛i参与。我们知道,在前$k$头奶牛中必定有一头奶牛不参与——对于$f[i][0]$转移很简单,由于奶牛$i$不参与,一定是选择继承,所以必定有$$f[i][0] = Max(f[i-1][0], f[i-1][1])$$. 而$f[i][1]$可以利用$f[i-j][0]$(0<j<K)来转移:$$f[i][1] = Max(f[i-j][0] + sum[i] - sum[i-j])$$
这个方程的意思就是$i-j$这头奶牛不选,并继承最优子结构$f[i-j][0]$,然后$i-j$之后的奶牛全部选择,于是用一个前缀和来维护即可。整理方程发现,$sum[i]$是确定的,于是可以将它提出$Max$之外,得到$$f[i][1] = Max(f[i-j][0] - sum[i-j]) + sum[i]$$我们发现这个方程就只与i-j有关了,并且是个定长区间的最大值——很容易让我们联想到滑动窗口问题,于是通过单调队列来解决就好了。
下面的代码贴的是以上之中方法……
刚才我们提到了可以用一维来解决,即$f[i]$表示前$i$头奶牛的最大效率。其实是与二维一模一样的,二维实在是多此一举。由于$i-j$根本不选,我们可以直接继承$f[i-j-1]$,在加上前缀和,就有了方程$$f[i][1] = Max(f[i-j-1] - sum[i-j]) + sum[i]$$
Code
long long
/*By QiXingzhi*/ #include <cstdio> #define N (100010) #define INF (0x3f3f3f3f) #define Max(a,b) (((a)>(b)) ? (a) : (b)) #define Min(a,b) (((a)<(b)) ? (a) : (b)) #define r read() typedef long long ll; #define int ll using namespace std; inline int read(){ ; ; register int c = getchar(); ')) c = getchar(); , c = getchar(); ) +(x << ) + c - ', c = getchar(); return x * w; } ,t; ],q[N],s[N]; inline void Push(int w){ ]-s[w] > f[q[t]][]-s[q[t]]) --t; q[++t] = w; } #undef int int main(){ #define int ll n=r,k=r; ; i <= n; ++i){ a[i]=r; s[i] = s[i-]+a[i]; } f[][] = ; f[][] = a[]; Push(); Push(); ; i <= n; ++i){ f[i][] = Max(f[i-][], f[i-][]); while(h<=t && q[h] < i-k) ++h; f[i][] = f[q[h]][] + s[i] - s[q[h]]; Push(i); } printf(],f[n][])); ; }