苏州本地网站建设,杭州室内设计公司排行榜,瑞安建设网站,网站建设 用什么语言NOIP2023模拟8联测29 C. 蛋糕 文章目录 NOIP2023模拟8联测29 C. 蛋糕题目大意思路code 题目大意
你现在得到了一个二维蛋糕#xff0c;它从左到右可以分成 n n n 列#xff0c;每列高为 a i a_i ai 。对于每一列#xff0c;又可以从下到上分为 a i a_i ai 块#x…NOIP2023模拟8联测29 C. 蛋糕 文章目录 NOIP2023模拟8联测29 C. 蛋糕题目大意思路code 题目大意
你现在得到了一个二维蛋糕它从左到右可以分成 n n n 列每列高为 a i a_i ai 。对于每一列又可以从下到上分为 a i a_i ai 块并且最上面一块权值为 1 1 1 从上到下权值依次加 。每一列的最上面的权值为 的块的上表面有“奶油”。
你现在要把这一个蛋糕分成若干个矩形要求每一个矩形上都要有“奶油”也即每个矩形要包含至少一个权值为 1 1 1 的块。显然蛋糕中的每一格都必须被划分到恰好一个矩形内且矩形不能包含没有蛋糕的格子。
定义每一块矩形的代价为其每一行的最大值之和即 ∑ i l r ( max j − d u v i , j ) \sum_{i l}^r(\max_{j - d}^u v_{i , j}) ∑ilr(maxj−duvi,j) 。特别地对于宽列数为 1 1 1 的矩形代价为矩形内权值的最大值。请你最小化划分整个蛋糕的代价。 n ≤ 3000 n\le 3000 n≤3000
思路
考虑维护区间最大值和最小值的位置。
然后搞一个 d p l , r , k dp_{l , r , k} dpl,r,k 表示区间 [ l , r ] [l , r] [l,r] 内从下往上前 k k k 层的最小代价。
通过一通推理发现对于一个区间 [ l , r ] [l , r] [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];
mapLL , 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;
}
