NOIP2023模拟8联测29 蛋糕

本文主要是介绍NOIP2023模拟8联测29 蛋糕，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

有一块二维蛋糕，它可以从左到右分成 $n$ 列，每列高为 $a_i$ 。对于每一列，又可以从下到上分为 $a_i$ 块，并且最上面的权值为 $1$ ，从上到下的权值依次加 $1$ 。每一列的最上面的权值为 $1$ 的块上有奶油。

1
2		1
3	1	2
4	2	3		1
5	3	4	1	2

你现在要把这个蛋糕分为若干个矩形，要求每个矩形上都有奶牛，即每个矩形要包含至少一个权值为 $1$ 的块。

定义每块矩形的代价为其每一行的最大值之和，即 $\sum\limits_{i=l}^r(\max\limits_{j=d}^u)v_{i,j}$ ，特别地，对于宽为 $1$ 的矩形（即列数为 $1$ 的矩形），代价为矩形内权值的最大值。请你最小化划分整个蛋糕的代价，并输出这个最小代价。

$1\leq n\leq 3000,1\leq a_i\leq 10^9$

题解

我们可以想到用 $D P$ 。设 $f_{l,r,k}$ 表示区间 $[l, r]$ 内都减去了 $k$ 的答案，那么答案为 $f_{1,n,0}$ ，状态数为 $O(n^3)$ ，暴力转移是 $O (n)$ 的。

考虑优化转移。我们考虑枚举区间最大值的最底下的块怎么划分：

选择最大值所在的一列作为一个矩形，两边分别处理
否则，选择将整个区间减去区间最小值一定最优。假设选择 $[l, r]$ 的子区间 $[x, y]$ 减去其区间最小值更优，则先减去 $[l, r]$ 的区间最小值再减去 $[x, y]$ 的区间最小值的代价相同，且还多选择了两边的部分，这样更优，与假设矛盾。得证选择将整个区间减去区间最小值最优

如果有多个最大值，则任意选择一个即可。

那么，转移就变成 $O (1)$ 的了。

但这样的话，时间复杂度是 $O(n^3)$ 的，还是过不了。不过，我们发现，如果打一个记搜就可以过了，这是因为有效状态实际上是 $O(n^2)$ 的，证明如下：

如果 $f_{l,r,k}$ 有可能在求 $f_{1,n,0}$ 中被用到，则需要满足如下两个条件：

$l = 1$ 或 $a_{l-1}<k$ 或 $a_{l-1}>\max\limits_{l\leq i\leq r}a_i$
$r = n$ 或 $a_{r+1}<k$ 或 $a_{r+1}>\max\limits_{l\leq i\leq r}a_i$

具体来说就是要么在 $[1, n]$ 的端点，要么在缩小边界时用最大值缩小或最小值缩小。

对于每一个 $k$ ，其满足条件的 $[l, r]$ 的数量实际上是 $O (n)$ 的。我们将所有 $a_i>k$ 的极长段来建大根笛卡尔树，每次删去其中一棵树的根节点（对应删去区间最大值的一列）会使合法区间增加最多两个，而最多会删去 $O (n)$ 个点，所以只会有 $O (n)$ 个有效区间。而 $k$ 的数量是 $O (n)$ 的，所以有效区间的总数为 $O(n^2)$ 。

因为在记搜时存储每种有效状态的答案要用 $\text{map}$ ，所以时间复杂度还要套一个 $O(\log n)$ 。

时间复杂度为 $O(n^2\log n)$ 。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3000,inf=2e9;
int n,a[N+5],mx[N+5][N+5],mn[N+5][N+5];
map<ll,ll>dp;
ll gt(ll l,ll r,ll k){return (l*(N+1)+r)*inf+k;
}
ll gtsum(ll v1,ll v2){return (v1+v2)*(v2-v1+1)/2;
}
ll solve(int l,int r,int k){ll w=gt(l,r,k);if(dp.count(w)) return dp[w];int mxd=mx[l][r],mnd=mn[l][r];ll re=a[mxd]-k;if(mxd!=l) re+=solve(l,mxd-1,k);if(mxd!=r) re+=solve(mxd+1,r,k);if(l!=r){ll tmp=gtsum(a[mxd]-a[mnd]+1,a[mxd]-k);if(mnd!=l) tmp+=solve(l,mnd-1,a[mnd]);if(mnd!=r) tmp+=solve(mnd+1,r,a[mnd]);re=min(re,tmp);}return dp[w]=re;
}
int main()
{freopen("cake.in","r",stdin);freopen("cake.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){mx[i][i]=mn[i][i]=i;for(int j=i+1;j<=n;j++){if(a[j]>a[mx[i][j-1]]) mx[i][j]=j;else mx[i][j]=mx[i][j-1];if(a[j]<a[mn[i][j-1]]) mn[i][j]=j;else mn[i][j]=mn[i][j-1];}}printf("%lld",solve(1,n,0));return 0;
}