题解：CF1787C Remove the Bracket
O_Yeee
·
·
题解
题目传送门。
首先观察最终求解的这个式子：
F = a_1 \cdot x_2+y_2 \cdot x_3+y_3 \cdot x_4 + y_4 \cdot \ldots \cdot x_{n-1}+y_{n-1} \cdot a_n
一个贪心是显而易见的：因为我们要使 F 最小，所以就要使每个 x_i 和 y_i 尽量的小。
而 (x_i-s) \cdot (y_i-s)\geq 0。这就告诉我们：我们选 x_i 和 y_i 的时候要尽量靠近这个 s 。所以说每个 x_{i_{min}} 和 y_{i_{min}} 就为 a_i-s 或 s。
但是简单的贪心并不适用于这个题，因为若贪心策略是你每次选择最小的那个数，显然有：
minn_{i-1} \times minn_{i} + maxx_{j-1} \times maxx_{j} \nless minn_{i-1}\times maxx_{j-1}+minn_{i} \times maxx_{j}
（即小数 小数 + 大数 大数 不一定优于 小数 大数 + 小数 大数）
所以我们只能用其他方法做。
继续观察原式我们可以发现它满足 dp 的条件：
- 当取到第 i 个数时，决策只与前面的值有关，并且在选了这个数后在当前一定最优。
- 每次选只与前面一项有关系。
其实用一个图更好理解：（图丑见谅）
可以发现在每次的答案只与 x_{i+1} 和 y_{i} 有关
所以我们可以设出 dp 状态。
令 dp_{i,0/1} 表示在 i 位置时 x 取 a_i-s 还是 s。
由上面的图可以清晰发现转移式子非常好想。
dp_{i,0}=\min(dp_{i-1,0}+y_{i,1} \times x_{i+1,0},dp_{i-1,1}+y_{i,0} \times x_{i+1,0})
即为上一个的和加上这一次取 s 值 或取 a_i-s 值的最小值。
$$ dp_{i,1}=\min(dp_{i-1,0}+y_{i,1} \times x_{i+1,1},dp_{i-1,1}+y_{i,0} \times x_{i+1,1})$$
最后 $dp_{n,0}$ 和 $dp_{n,1}$ 取 $min$ 即为答案。
有一个疑问可能是若 $s+1$ 和 $a_i-s-1$ 比 $s$ 和 $a_i$ 更优的话怎么办，那样一定可以优化为 $a_i-s$ 和 $s$ 这种情况，我们的 $x_{i,0},y_{i,0},x_{i,1},y_{i,1}$ 保证了这两种情况一定会讨论到，就没有问题。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N],dp[N][2],x[N][2],y[N][2];
int read(){
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
x=(x<<3)+(x<<1)+ch-48;
ch=getchar();
}
return x*f;
}
void Main(){
//cf多测千万不要用，会TLE
// memset(a,0,sizeof(a));
// memset(dp,0,sizeof(dp));
// memset(x,0,sizeof(x));
// memset(y,0,sizeof(y));
int n,s;
n=read(),s=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=2;i<n;i++){
if(a[i]>=s)
{
x[i][0]=s,x[i][1]=a[i]-s;
y[i][0]=s,y[i][1]=a[i]-s;
}
else {
x[i][0]=a[i],x[i][1]=0;//注意<0时要特判
y[i][0]=a[i],y[i][1]=0;
}
dp[i][0]=dp[i][1]=0;
}
y[1][0]=y[1][1]=a[1];
x[n][0]=x[n][1]=a[n];//注意初始化
for(int i=1;i<n;i++){
dp[i][0]=min(dp[i-1][0]+y[i][1]*x[i+1][0],dp[i-1][1]+y[i][0]*x[i+1][0]);
dp[i][1]=min(dp[i-1][0]+y[i][1]*x[i+1][1],dp[i-1][1]+y[i][0]*x[i+1][1]);
}
printf("%lld\n",min(dp[n-1][0],dp[n-1][1]));
}
signed main(){
int T;T=read();
while(T--)Main();
return 0;
}
```