CF354D Transferring Pyramid 做题记录

一个 $n$ 层的金字塔，你能进行两种操作。

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

现在有 $m$ 个黑点，求出把所有黑点染色所需的最小代价。

$1\le n,m\le 10^5$。

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

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

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

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

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

不难发现，答案上界是 $3m$，也就是说选择的直角三角形的左上角的高度 $x$ 不会大于 $\sqrt{6m}\approx 774$，所以时间复杂度可以优化到 $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;
}