一个 层的金字塔,你能进行两种操作。
给某个点染色,代价是 。给某一个底边是金字塔的底边的子三角形染色,,代价是 。
现在有 个黑点,求出把所有黑点染色所需的最小代价。
。
模拟赛的时候读错题了……
首先可以把金字塔向左对齐,并且把行数从下到上重新编号(),这样问题就变成了选一个点染色或者选一个“到底”的直角三角形染色。
从左向右一列一列考虑,假设考虑到 ,显然左上角在 这一列前面的所有直角三角形都处理完了,并且这些直角三角形会在当前列即以后留下一个“小尖”:

那么有一个显然的 dp,设 表示处理完前 列,所有直角三角形在第 列的左上角最高为 (即“小尖”和在第 列选的直角三角形覆盖了第 列 以下的所有点)需要的最少花费。
转移枚举当前列选的直角三角形即可,前缀最小值加上后缀和可以优化到 。
不难发现,答案上界是 ,也就是说选择的直角三角形的左上角的高度 不会大于 ,所以时间复杂度可以优化到 ,加上滚动数组优化即可通过本题。
代码如下:
#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;
}