CF354D Transferring Pyramid 做题记录

一个 nn 层的金字塔,你能进行两种操作。

给某个点染色,代价是 33。给某一个底边是金字塔的底边的子三角形染色,,代价是 点数+2\text{点数}+2

现在有 mm 个黑点,求出把所有黑点染色所需的最小代价。

1n,m1051\le n,m\le 10^5

模拟赛的时候读错题了……

首先可以把金字塔向左对齐,并且把行数从下到上重新编号(xnx+1x\to n-x+1),这样问题就变成了选一个点染色或者选一个“到底”的直角三角形染色。

从左向右一列一列考虑,假设考虑到 ii,显然左上角在 ii 这一列前面的所有直角三角形都处理完了,并且这些直角三角形会在当前列即以后留下一个“小尖”:

那么有一个显然的 dp,设 dpi,jdp_{i,j} 表示处理完前 ii 列,所有直角三角形在第 ii 列的左上角最高为 jj(即“小尖”和在第 ii 列选的直角三角形覆盖了第 iijj 以下的所有点)需要的最少花费。

转移枚举当前列选的直角三角形即可,前缀最小值加上后缀和可以优化到 O(n2)O(n^2)

不难发现,答案上界是 3m3m,也就是说选择的直角三角形的左上角的高度 xx 不会大于 6m774\sqrt{6m}\approx 774,所以时间复杂度可以优化到 O(774n)O(774n),加上滚动数组优化即可通过本题。

代码如下:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int S=100005,MS=785;

int n,m,lim;
vector<int> pos[S];
int dp[2][MS];

int main()
{
	scanf("%d%d",&n,&m);
	lim=min(n,MS-3);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		pos[y].push_back(n-x+1);
	}
	for(int i=1;i<=n;i++) sort(pos[i].begin(),pos[i].end());
	memset(dp,127,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		int u=i&1,v=i-1&1;
		memset(dp[u],127,sizeof(dp[u]));
		int k=0,siz=pos[i].size();
		dp[u][0]=dp[v][0]+(siz-k)*3;
		for(int j=0,k=0;j+1<=lim&&j<=n-i+1;j++)
		{
			while(k<pos[i].size()&&pos[i][k]<=j) k++;
			dp[u][j]=min(dp[u][j],dp[v][j+1]+(siz-k)*3);
		}
		k=0;
		int mn=min(dp[v][0],dp[v][1]);
		for(int j=1;j<=lim&&j<=n-i+1;j++)
		{
			while(k<pos[i].size()&&pos[i][k]<=j) k++;
			if(j+1<=lim) mn=min(mn,dp[v][j+1]);
			dp[u][j]=min(dp[u][j],mn+j*(j+1)/2+2+(siz-k)*3);
		}
	}
	printf("%d\n",min(dp[n&1][0],dp[n&1][1]));
	return 0;
}