NOIP2023模拟8联测29 C. 蛋糕

• NOIP2023模拟8联测29 C. 蛋糕
  • 题目大意
  • 思路
  • code

题目大意

你现在得到了一个二维蛋糕，它从左到右可以分成 \(n\) 列，每列高为 \(a_i\) 。对于每一列，又可以从下到上分为 \(a_i\) 块，并且最上面一块权值为 \(1\) ，从上到下权值依次加 。每一列的最上面的权值为 的块的上表面有“奶油”。

你现在要把这一个蛋糕分成若干个矩形，要求每一个矩形上都要有“奶油”，也即每个矩形要包含至少一个权值为 \(1\) 的块。显然蛋糕中的每一格都必须被划分到恰好一个矩形内，且矩形不能包含没有蛋糕的格子。

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

\(n\le 3000\)

思路

考虑维护区间最大值和最小值的位置。

然后搞一个 \(dp_{l , r , k}\) 表示区间 \([l , r]\) 内从下往上前 \(k\) 层的最小代价。

通过一通推理发现，对于一个区间 \([l , r]\) 的最优策略就是删除最高的那一列或者把区间的所有蛋糕删到最矮的那一列那么高。

搞一个记忆化就好了

code

#include <bits/stdc++.h>
#define LL long long
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int N = 3005;
int n , min1[N][N] , max1[N][N];
LL a[N];
map<LL , LL> dp;
LL gt (LL l , LL r , LL k) { return (l * (N + 1) + r) * N + k; }
LL getsum (LL x , LL y) { return (x + y) * (y - x + 1) / 2; }
LL solve (int l , int r , LL k) {
	LL id = gt (l , r , k);
	if (dp.count (id)) return dp[id];
	int mxd = max1[l][r] , mnd = min1[l][r];
	LL ans = a[mxd] - k;
	if (mxd > l) ans += solve (l , mxd - 1 , k);
	if (mxd < r) ans += solve (mxd + 1 , r , k);
	if (l != r) {
		LL ans1 = getsum (a[mxd] - a[mnd] + 1 , a[mxd] - k);
		if (l < mnd) ans1 += solve (l , mnd - 1 , a[mnd]);
		if (mnd < r) ans1 += solve (mnd + 1 , r , a[mnd]);
		ans = min (ans , ans1);
	}
	return dp[id] = ans;
}
int main () {
	freopen ("cake.in" , "r" , stdin);
	freopen ("cake.out" , "w" , stdout);
	scanf ("%d" , &n); 
	fu (i , 1 , n) {
		scanf ("%lld" , &a[i]);
	}
	fu (l , 1 , n) {
		min1[l][l] = max1[l][l] = l;
		fu (r , l + 1 , n) {
			min1[l][r] = min1[l][r - 1] , max1[l][r] = max1[l][r - 1];
			if (a[min1[l][r - 1]] > a[r]) min1[l][r] = r;
			if (a[max1[l][r - 1]] < a[r]) max1[l][r] = r;
		}
	}
//	return 0;
	printf ("%lld" , solve (1 , n , 0));
	return 0;
}