题解 P6563 【[SBCOI2020] 一直在你身旁】
devout
2020-11-21 14:27:37
显然有一个 $O(n^3)$ 的暴力dp，设 $f_{i,j}$ 表示确定一个值在区间 $[l,r]$ 上的最小花费，那么显然有转移
$$f_{i,j}=\min\{\max(f_{i,k},f_{k+1,j})+a_k\}$$
根据区间dp的做法就可以解决了。
考虑优化，我们可以注意到，对于 $i$ 固定时，$f_{i,j}$ 是单调不减的，$j$ 固定时，$f_{i,j}$ 是单调不增的，所以对于一个区间 $[i,j]$，我们一定可以找到一个位置 $x$，是的对于 $\forall k\in[i,x],f_{i,k}<f_{k+1,j},\forall k\in(x,j],f_{i,k}>f_{k+1,j}$
并且我们观察到，当 $j$ 固定的时候，显然决策点 $x$ 随着 $i$ 的减小而单调不增。
我们考虑先枚举 $j$，然后倒序枚举 $i$
所以可以考虑把转移分成两部分，对于在 $x$ 左边的部分，即用 $\min\{f_{k+1,j}+a_k\}$ 的部分转移的，我们可以用单调队列维护，对于在 $x$ 右边的部分，$f_{i,k}$单调不减，$a_k$ 单调不减，所以最优决策点一定在 $x+1$ 的位置上
这样一来，总复杂度就可以做到 $O(n^2)$ 了。
代码比较短，但是写起来真的是费劲：
```cpp
#include <bits/stdc++.h>
using namespace std;
# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
typedef long long ll;
const int N=7100;
template<typename T> void read(T &x){
x=0;int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
x*=f;
}
int t,n;
int a[N];
ll f[N][N];
int q[N],head,tail;
int main()
{
memset(f,0x3f,sizeof(f));
read(t);
while(t--){
read(n);
Rep(i,1,n)read(a[i]);
Rep(i,1,n)f[i][i]=0;
for(int j=1;j<=n;j++){
head=1,tail=0;
int k=j-1;
for(int i=j-1;i;i--){
while(k>=i&&f[i][k]>f[k+1][j])k--;
while(head<=tail&&q[head]>k)head++;
while(head<=tail&&f[q[tail]+1][j]+a[q[tail]]>f[i+1][j]+a[i])tail--;
q[++tail]=i;
f[i][j]=min(f[i][j],f[i][k+1]+a[k+1]);
f[i][j]=min(f[i][j],f[q[head]+1][j]+a[q[head]]);
}
}
printf("%lld\n",f[1][n]);
Rep(i,1,n)Rep(j,1,n)f[i][j]=1e18;
}
return 0;
}
```