I题: The Great Wall II

原题链接:https://ac.nowcoder.com/acm/contest/33194/I

题目大意

有长度为 $n(1\le n\le 8000)$ 的序列 $a$ 。将其分为 $k$ 个非空连续区间的代价是每个区间内 $a_i$ 的最大值的总和。对于每个 $k\in [1,n]$ ，输出最小的代价。

题解

考虑动态规划，设 $f_{k,i}$ 表示将前 $i$ 个数字分为 $k$ 的最小代价。
易得朴素转移式:
$$f_{k,i}=\underset{x=1}{\overset{i}{\min }}(f_{k-1,x-1}+\underset{y=x}{\overset{i}{\max }}{a}_y)$$

暴力转移复杂度为 $O(n^3)$ ， 不可行，考虑优化转移复杂度。
不难发现，当第二项 $\underset{y=x}{\overset{i}{\max }}{a}_y$ 确定时，对 $f_{k-1,x-1}$ 取最小值即可。
$\underset{y=x}{\overset{i}{\max }}{a}_y$ 可画出大致图像如下:

该项具有单调性，可以用单调栈维护每一个 $\underset{y=x}{\overset{i}{\max }}{a}_y$ ，同时维护其对应范围内的 $\min f_{k-1,x-1}$ 即可。
当 $i$ 增加时，图像可能变化为如下状态:


(绿色为更新的部分，紫色为更新后的有效部分)
我们可以对新的 $\underset{y=x}{\overset{i}{\max }}{a}_y$ (绿色部分)在弹出单调栈顶元素的过程中用已有的(第二张图红色部分) $\min f_{k-1,x-1}$ 来更新新的 $\min f_{k-1,x-1}$ 。
设 $m{n}_i$ 表示 $\underset{y=x}{\overset{i}{\max }}{a}_y=a_i$ 范围内的 $\min f_{k-1,x-1}$ 。
最终答案应为 $f_{k,i}=\min (\underset{j\in stack}{\min }(m{n}_j+v_j),m{n}_i+a_i)$ ，然后将 $i$ 放入单调栈即可。
实际上 $f_{k,top}=\underset{j\in stack}{\min }(m{n}_j+v_j)$ ，故转移式可简化为 $f_{k,i}=\min (f_{k,top},m{n}_i+a_i)$ 。
动态规划复杂度为 $O(n^2)$ ， $n$ 次单调栈复杂度也为 $O(n^2)$ ，可以通过此题。

注意到更新 $f_{k,i}$ 只需要 $f_{k-1,j}$ ，可以用滚动数组优化内存。

参考代码

#include
using namespace std;

template<class T>inline void read(T&x){
   char c,last=' ';
   while(!isdigit(c=getchar()))last=c;
   x=c^48;
   while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
   if(last=='-')x=-x;
}

const int MAXN=8e3+5;
int n;
int a[MAXN];
int mn[MAXN];//范围内最小的f
int stk[MAXN],top;//单调栈
int f[MAXN],g[MAXN];//滚动数组

int main()
{
   read(n);
   for(int i=1;i<=n;++i)read(a[i]);
   memset(g,0x3f,sizeof(g));
   g[0]=0;
   for(int k=1;k<=n;++k){
   	f[top=0]=0x3f3f3f3f;//top=0清空栈，同时将f[0]赋值为inf防止空栈时转移出错
   	for(int i=k;i<=n;++i){
   		mn[i]=g[i-1];
   		while(top&&a[stk[top]]<=a[i]){//单调栈
   			mn[i]=min(mn[i],mn[stk[top]]);//维护mn
   			--top;
   		}
   		f[i]=min(f[stk[top]],mn[i]+a[i]);//转移
   		stk[++top]=i;//将i压入栈中
   	}
   	for(int i=k;i<=n;++i)g[i]=f[i];
		cout<<f[n]<<'\n';//答案即f[n]
   }
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40