【题目链接】

ybt 1612：特别行动队
洛谷 P3628 [APIO2010] 特别行动队

【题目考点】

1. 动态规划：斜率优化动规

斜率优化的具体原理、和代码细节参考模板题：
信息学奥赛一本通 1607：【 例 2】任务安排 2 | 洛谷 P10979 任务安排 2

【解题思路】

给定整数序列$x$，每个整数是一个元素，每个行动队是该序列的一个子段。根据计算可以得到该行动队的战斗力，将战斗力叫做费用

状态定义

• 阶段：前i个元素
• 决策：是否将第i加入子段
• 策略：子段划分的方案
• 策略集合：前i个元素的所有子段划分方案。
• 条件：费用最大
• 统计量：费用

状态定义$d{p}_i$：前i个元素的所有子段划分方案中，费用最大的方案的费用。
初始状态$d{p}_0=0$

状态转移方程

• 策略集合：前$i$个元素的所有子段划分方案。
• 分割策略集合：根据最后一个子段的起始位置分割策略集合。
  记最后一个子段的起始位置为$j+1$，$j$最小为$0$，最大为$i-1$，因此$0\le j\le i-1$
  前$j$个元素进制子段划分得到的最大费用为$d{p}_j$。
  第$j+1$到第$i$元素贡献的费用为：$x={\sum }_{k=j+1}^i{x}_k$，而后费用为$a{x}^2+bx+c$
  设$x$序列的前缀和为$sx$，则$x=s{x}_i-s{x}_j$，所需费用为$a(s{x}_i-s{x}_j{)}^2+b(s{x}_i-s{x}_j)+c$
  对于$j$的所有可能取值，取费用的最小值。
  状态转移方程为：
  d p i = m i n { d p j + a ( s x i − s x j ) 2 + b ( s x i − s x j ) + c } ， 0 ≤ j ≤ i − 1 dp_i=min\{dp_j+a(sx_i-sx_j)^2+b(sx_i-sx_j)+c\}，0\le j \le i-1 dpi​=min{dpj​+a(sxi​−sxj​)2+b(sxi​−sxj​)+c}，0≤j≤i−1

进行斜率优化动规，去掉min，将与$j$相关的表达式视为变量
$-d{p}_j=-d{p}_i+a(s{x}_i^2-2s{x}_i\cdot s{x}_j+s{x}_j^2)+b\cdot s{x}_i-b\cdot s{x}_j+c$
$-d{p}_j-a\cdot s{x}_j^2+b\cdot s{x}_j=-2a\cdot s{x}_i\cdot s{x}_j-d{p}_i+a\cdot s{x}_i^2+b\cdot s{x}_i+c$

解法1: 斜率$k$随着$i$的增大单调递增

（建议将斜率$k$设计为随着$i$的增大单调递增，这样方便写固定的模板代码，减少出错。）
设：
$y=-d{p}_j-a\cdot s{x}_j^2+b\cdot s{x}_j$，
$x=s{x}_j$
$k=-2a\cdot s{x}_i$
$b=-d{p}_i+a\cdot s{x}_i^2+b\cdot s{x}_i+c$
则该方程为$y=kx+b$，直线斜率固定，看过哪个决策点$(s{x}_j,-d{p}_j-a\cdot s{x}_j^2+b\cdot s{x}_j)$时直线截距最小，此时$d{p}_i$最大。
由于已知$a<0$，直线斜率$k=-2a\cdot s{x}_i$随着$i$的增大而增大。
使用单调队列$q$维护决策点集的下凸壳，$q_l$是队头，$q_r$是队尾。单调队列中相邻两决策点连线的斜率是单调递增的。
$K(a,b)$是$a$、$b$两个决策点连线的斜率。
每次循环新加入决策点为$j=i-1$，只要$K(q_r,i-1)\le K(q_{r-1},q_r)$，则队尾出队，当$K(q_r,i-1)>K(q_{r-1},q_r)$时将$i-1$队尾入队。
只要$K(q_l,q_{l+1})\le -2a\cdot s{x}_i$，则队头出队。
队头$q_l$就是最优决策点，令$j=q_l$，代入状态转移方程，求出$d{p}_i$。
最终结果为$d{p}_n$

解法2: 斜率$k$随着$i$的增大单调递减

$-d{p}_j-a\cdot s{x}_j^2+b\cdot s{x}_j=-2a\cdot s{x}_i\cdot s{x}_j-d{p}_i+a\cdot s{x}_i^2+b\cdot s{x}_i+c$
等号两侧乘以$-1$得：
$d{p}_j+a\cdot s{x}_j^2-b\cdot s{x}_j=2a\cdot s{x}_i\cdot s{x}_j+d{p}_i-a\cdot s{x}_i^2-b\cdot s{x}_i-c$

设：
$y=d{p}_j+a\cdot s{x}_j^2-b\cdot s{x}_j$，
$x=s{x}_j$
$k=2a\cdot s{x}_i$
$b=d{p}_i-a\cdot s{x}_i^2-b\cdot s{x}_i-c$
则该方程为$y=kx+b$，直线斜率固定，看过哪个决策点$(s{x}_j,d{p}_j+a\cdot s{x}_j^2-b\cdot s{x}_j)$时直线截距最大，此时$d{p}_i$最大。
由于已知$a<0$，直线斜率$k=2a\cdot s{x}_i$随着$i$的增大而减小。
使用单调队列$q$维护决策点集的上凸壳，$q_l$是队头，$q_r$是队尾。单调队列中相邻两决策点连线的斜率是单调递减的。
$K(a,b)$是$a$、$b$两个决策点连线的斜率。
每次循环新加入决策点为$j=i-1$，只要$K(q_r,i-1)\ge K(q_{r-1},q_r)$，则队尾出队。当$K(q_r,i-1)<K(q_{r-1},q_r)$时将$i-1$队尾入队。
只要$K(q_l,q_{l+1})\ge 2a\cdot s{x}_i$，则队头出队。
队头$q_l$就是最优决策点，令$j=q_l$，代入状态转移方程，求出$d{p}_i$。
最终结果为$d{p}_n$

【题解代码】

解法1：斜率$k$随着$i$的增大单调递增

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
typedef long long LL;
LL n, a, b, c, x[N], sx[N], dp[N];
int q[N], l = 1, r = 0;
LL X(int j)
{
	return sx[j];
}
LL Y(int j)
{
	return -dp[j]-a*sx[j]*sx[j]+b*sx[j];
}
LL K(int i)
{
	return -2*a*sx[i];
}
bool cmp(LL y1, LL x1, LL y2, LL x2)//y1/x1 <= y2/x2
{
	return y1*x2 <= y2*x1;
}
int main()
{
	cin >> n >> a >> b >> c;
	for(int i = 1; i <= n; ++i)
	{
		cin >> x[i];
		sx[i] = sx[i-1]+x[i];
	}
	for(int i = 1; i <= n; ++i)
	{
		while(l < r && cmp(Y(i-1)-Y(q[r]), X(i-1)-X(q[r]), Y(q[r])-Y(q[r-1]), X(q[r])-X(q[r-1])))
			r--;
		q[++r] = i-1;
		while(l < r && cmp(Y(q[l+1])-Y(q[l]), X(q[l+1])-X(q[l]), K(i), 1))
			l++;
		dp[i] = dp[q[l]]+a*(sx[i]-sx[q[l]])*(sx[i]-sx[q[l]])+b*(sx[i]-sx[q[l]])+c;
	}
	cout << dp[n];
	return 0;
}

解法2：斜率$k$随着$i$的增大单调递减

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
typedef long long LL;
LL n, a, b, c, x[N], sx[N], dp[N];
int q[N], l = 1, r = 0;
LL X(int j)
{
	return sx[j];
}
LL Y(int j)
{
	return dp[j]+a*sx[j]*sx[j]-b*sx[j];
}
LL K(int i)
{
	return 2*a*sx[i];
}
bool cmp(LL y1, LL x1, LL y2, LL x2)//y1/x1 >= y2/x2
{
	return y1*x2 >= y2*x1;
}
int main()
{
	cin >> n >> a >> b >> c;
	for(int i = 1; i <= n; ++i)
	{
		cin >> x[i];
		sx[i] = sx[i-1]+x[i];
	}
	for(int i = 1; i <= n; ++i)
	{
		while(l < r && cmp(Y(i-1)-Y(q[r]), X(i-1)-X(q[r]), Y(q[r])-Y(q[r-1]), X(q[r])-X(q[r-1])))
			r--;
		q[++r] = i-1;
		while(l < r && cmp(Y(q[l+1])-Y(q[l]), X(q[l+1])-X(q[l]), K(i), 1))
			l++;
		dp[i] = dp[q[l]]+a*(sx[i]-sx[q[l]])*(sx[i]-sx[q[l]])+b*(sx[i]-sx[q[l]])+c;
	}
	cout << dp[n];
	return 0;
}