题目

分析

毫无疑问 \(dp\)

设 \(f_{i,j}\) 表示选到第 \(i\) 层，已选 \(j\) 个矩阵最大覆盖面积

那么 \(f_{i,j}=\max{f_{l,j}+w_i*(i-l)}\)

显然斜率优化

\(Code\)

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long LL;

int n , k , q[20005];

LL f[20005][105];

struct node{

	int x , y , w;

}p[20005];

double slope(int j , int l , int r)

{

	return 1.0 * (f[l][j] - f[r][j]) / (l - r);

}

int main()

{

	freopen("pyramid.in" , "r" , stdin);

	freopen("pyramid.out" , "w" , stdout);

	scanf("%d%d" , &n , &k);

	for(register int i = 1; i <= n; i++)

		scanf("%d%d" , &p[i].x , &p[i].y) , p[i].w = p[i].y - p[i].x + 1;

	int h , t;

	for(register int j = 1; j <= k; j++)

	{

		h = t = 1;

		for(register int i = 1; i <= n; i++)

		{

			while (h < t && slope(j - 1 , q[h + 1] , q[h]) > p[i].w) h++;

			f[i][j] = f[q[h]][j - 1] + 1LL * p[i].w * (i - q[h]);

			while (h <= t && slope(j - 1 , q[t] , q[t - 1]) < slope(j - 1 , i , q[t])) t--;

			q[++t] = i;

		}

	}

	LL ans = 0;

	for(register int i = 1; i <= n; i++) ans = max(ans , f[i][k]);

	printf("%lld" , ans);

}

巴特西

JZOJ 5347. 【NOIP2017提高A组模拟9.5】遥远的金字塔

题目

分析

\(Code\)

最新文章

热门文章