本题可以想到，设 f i f_i fi为前 i i i头牛合法选择的最大效益。首先可以不选， f i = f i − 1 f_i=f_{i-1} fi=fi−1。考虑选择第 i i i头牛，可以枚举一个 j j j表示 i i i开始往前连续的牛的数量，保证 1 ≤ j ≤ k 1\le j\le k 1≤j≤k即可。则这一段牛就是 ∑ x = i − j + 1 i \displaystyle\sum_{x=i-j+1}^i x=i−j+1∑i，为了保证不选第 i − j i-j i−j头牛，那么就是用 f i − j − 1 f_{i-j-1} fi−j−1。于是有状态转移方程 f i = max ( f i − 1 , max ( f i − j − 1 + ∑ x = i − j + 1 i , 1 ≤ j ≤ k ) ) f_i=\max(f_{i-1},\max(f_{i-j-1}+\displaystyle\sum_{x=i-j+1}^i,1\le j\le k)) fi=max(fi−1,max(fi−j−1+x=i−j+1∑i,1≤j≤k))。有了状态转移方程，发现有一个求区间和的过程，用前缀和。发现中间的 j j j求的是一个 max \max max，可以用单调队列维护。因为 f f f可以从 f 0 f_0 f0迭代，所以要先压入一个 0 0 0。
#include<bits/stdc++.h> using namespace std; const int NN=1e5+4; long long s[NN],f[NN]; int q[NN]; int main() { int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%lld",&s[i]); s[i]+=s[i-1]; } int h=0,t=0; for(int i=1;i<=n;i++) { if(q[h]<i-k) h++; if(h<=t) f[i]=max(f[i-1],f[q[h]-1]+s[i]-s[q[h]]); while(h<=t&&f[q[t]-1]-s[q[t]]<=f[i-1]-s[i]) t--; q[++t]=i; } printf("%lld",f[n]); return 0; }本题和上讲的AcWing 1089非常像。考虑如何转换成那一题，发现本题中缺少的就是连续不选择的限制，这也刚好是本题要求的，那么就二分答案。然后有了这个限制，按那一题的做法计算最少用的代价，看看能不能有一种方法在 t t t的时间内完成，这就是二分答案的 c h e c k check check函数。因为 f f f可以从 f 0 f_0 f0迭代，所以要先压入一个 0 0 0。
#include<bits/stdc++.h> using namespace std; const int NN=5*1e4+4; int n,t,a[NN],f[NN],q[NN]; bool check(int mid) { int head=0,tail=0; for(int i=1;i<=n;i++) { if(q[head]+mid+1<i) head++; if(head<=tail) f[i]=f[q[head]]+a[i]; while(f[q[tail]]>=f[i]&&head<=tail) tail--; q[++tail]=i; } for(int i=n-mid;i<=n;i++) if(f[i]<=t) return true; return false; } int main() { scanf("%d%d",&n,&t); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int l=1,r=n; while(l<r) { int mid=l+(r-l)/2; if(check(mid)) r=mid; else l=mid+1; } printf("%d",r); return 0; }本题是一个二维的滑动窗口。可以先竖着求一遍在 n n n行内的最小值和最大值，这样就相当于把 n n n行压缩成一个数，这样就压缩了一维。然后再横着求一边一维的滑动窗口即可。
#include<bits/stdc++.h> using namespace std; const int NN=1004; int g[NN][NN],maxn[NN][NN],minn[NN][NN],q1[NN],q2[NN]; int main() { int a,b,n,ans=1e9,h1,h2,t1,t2; scanf("%d%d%d",&a,&b,&n); for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) scanf("%d",&g[i][j]); for(int i=1;i<=a;i++) { h1=0; h2=0; t1=-1; t2=-1; for(int j=1;j<=b;j++) { if(h1<=t1&&q1[h1]<=j-n) h1++; if(h2<=t2&&q2[h2]<=j-n) h2++; while(h1<=t1&&g[i][q1[t1]]<=g[i][j]) t1--; while(h2<=t2&&g[i][q2[t2]]>=g[i][j]) t2--; q1[++t1]=q2[++t2]=j; if(h1<=t1&&j>=n) maxn[i][j-n+1]=g[i][q1[h1]]; if(h2<=t2&&j>=n) minn[i][j-n+1]=g[i][q2[h2]]; } } for(int i=1;i<=b-n+1;i++) { h1=0; h2=0; t1=-1; t2=-1; for(int j=1;j<=a;j++) { if(h1<=t1&&q1[h1]<=j-n) h1++; if(h2<=t2&&q2[h2]<=j-n) h2++; while(h1<=t1&&maxn[q1[t1]][i]<=maxn[j][i]) t1--; while(h2<=t2&&minn[q2[t2]][i]>=minn[j][i]) t2--; q1[++t1]=q2[++t2]=j; if(h1<=t1&&h2<=t2&&j>=n) ans=min(ans,maxn[q1[h1]][i]-minn[q2[h2]][i]); } } printf("%d",ans); return 0; }斜率优化，指的是一些形如 y = k x + b y=kx+b y=kx+b的状态转移方程，利用 k k k的单调性的优化。其中， k k k和 b b b是常量。
一般来说都会是和单调队列优化并用。首先，常量就是不变的数，而用于迭代的是找的最小的，所以不能放在 k k k和 b b b中，只能放在 x x x和 y y y中。得到了这样一个方程，每次加入一个点 i i i（横坐标 x x x，纵坐标 y y y）就说明 i i i可以作为以后的 j j j。在斜率相邻的两点之间连一条边。因为 f i f_i fi是常量且没有系数，所以 f i f_i fi应该是放在截距里面的。于是我们可以得到下图： 假设是一个求 m i n min min的状态转移方程，想找一个使 f i f_i fi最小的 j j j，那就是使 b b b最小。所以现在假设有多个点，那第一个斜率比当前斜率高的边 x → y x\to y x→y中， x x x就是能使 f i f_i fi最小的 j j j，可以用二分来找。然后，判断自己是否在点内部，如果在外部就可以加入这个点集，看看从哪里连边斜率才单调递增并删掉其他的点，这些点都是会被包含在内的点。求最大值同理。
请注意，本题只是后面两题的铺垫，并不需要斜率优化。考虑状态转移，设 f i f_i fi表示完成前 i i i个任务所需的最小代价。枚举一个划分两批任务的分界点 j j j，则： f i = min ( f j + ∑ k = j + 1 i c k × ∑ k = 1 i t k + s × ∑ k = j + 1 n c k , 0 ≤ j < i ) f_i=\min(f_j+\displaystyle\sum_{k=j+1}^i c_k\times \displaystyle\sum_{k=1}^i t_k+s\times \displaystyle\sum_{k=j+1}^n c_k,0\le j<i) fi=min(fj+k=j+1∑ick×k=1∑itk+s×k=j+1∑nck,0≤j<i)因为有求一段区间的和的过程，所以要用前缀和优化。
#include<bits/stdc++.h> using namespace std; const int NN=5004; int t[NN],c[NN],f[NN]; int main() { int n,s; scanf("%d%d",&n,&s); for(int i=1;i<=n;i++) { scanf("%d%d",&t[i],&c[i]); t[i]+=t[i-1]; c[i]+=c[i-1]; } memset(f,0x3f,sizeof(f)); f[0]=0; for(int i=1;i<=n;i++) for(int j=0;j<i;j++) f[i]=min(f[i],f[j]+(c[i]-c[j])*t[i]+(c[n]-c[j])*s); printf("%d",f[n]); return 0; }本题就需要按上述方法去斜率优化了。先计算状态转移方程，原方程： f i = f j + ( c i − c j ) × t i + s × ( c n − c j ) f_i=f_j+(c_i-c_j)\times t_i+s\times (c_n-c_j) fi=fj+(ci−cj)×ti+s×(cn−cj)现在我们要用一个 j j j使这个式子更小，所以变量是 j j j。现在我们把变量放在正确的位置去： f j = ( s + t i ) × c j + f i − t i × c i − s × c n f_j=(s+t_i)\times c_j+f_i-t_i\times c_i-s\times c_n fj=(s+ti)×cj+fi−ti×ci−s×cn我们发现，本题中横坐标 x x x（就是 c j c_j cj）是单调递增的，所以新加的点一定在最右侧，一定不会包含在已经有的边内，可以直接删掉斜率较高的。我们又发现，斜率中 s s s是不变的， t t t是单调递增的，所以 s + t i s+t_i s+ti单调递增。因此，一条边比当前的斜率小，那一定也比以后的斜率小，直接删除即可。最后，如何计算两个点连的边的斜率呢？纵坐标之差除以横坐标之差即可。
#include<bits/stdc++.h> using namespace std; const int NN=3e5+4; long long c[NN],t[NN],f[NN]; int q[NN]; double doit(int x,int y) { return 1.0*(f[x]-f[y])/(c[x]-c[y]); } int main() { int n,s; scanf("%d%d",&n,&s); for(int i=1;i<=n;i++) { scanf("%lld%lld",&t[i],&c[i]); t[i]+=t[i-1]; c[i]+=c[i-1]; } int head=0,tail=0; for(int i=1;i<=n;i++) { while(head<tail&&doit(q[head+1],q[head])<=s+t[i]) head++; f[i]=f[q[head]]+t[i]*(c[i]-c[q[head]])+s*(c[n]-c[q[head]]); while(head<tail&&doit(q[tail],q[tail-1])>=doit(i,q[tail-1])) tail--; q[++tail]=i; } printf("%lld",f[n]); return 0; }这个题目 t t t可能是负数，所以不保证斜率是单调递增的，所以不能删除斜率小的边，而且要二分。本题的精度特别变态，所以这里改成用乘法。
#include<bits/stdc++.h> using namespace std; const int NN=3e5+4; int q[NN]; long long f[NN],t[NN],c[NN]; int main() { int n,s; scanf("%d%d",&n,&s); for(int i=1;i<=n;i++) { scanf("%lld%lld",&t[i],&c[i]); t[i]+=t[i-1]; c[i]+=c[i-1]; } int head=0,tail=0; for(int i=1;i<=n;i++) { int l=head,r=tail; while(l<r) { int mid=l+r>>1; if(f[q[mid+1]]-f[q[mid]]>(s+t[i])*(c[q[mid+1]]-c[q[mid]])) r=mid; else l=mid+1; } int j=q[r]; f[i]=f[j]-(s+t[i])*c[j]+t[i]*c[i]+s*c[n]; while(head<tail&&(double)(f[q[tail]]-f[q[tail-1]])*(c[i]-c[q[tail]])>=(double)(f[i]-f[q[tail]])*(c[q[tail]]-c[q[tail-1]])) tail--; q[++tail]=i; } printf("%lld",f[n]); return 0; }解析和代码在下一篇博客——最短路给出
