CF1842E Tenzing and Triangle 题解

题意不多赘述。

思路

如果两个所选的三角形有重合部分的话，那么这种情况肯定是不会出现的。因为如果把这两个三角形合成一个大三角形的话，不仅覆盖面积会增大，而且花费的代价还不会多。

于是我们可以想到用 dp 来解决，设 \(dp_{i}\) 表示删完横坐标为 \(0\) 到 \(i\) 中的点的最小代价，很容易得到状态转移方程：\(dp_{i}=\min(dp_{j}+(i-j-1)\times A+cost)\)。这里的 \(cost\) 指的是所有满足 \(j<x\le i,1\le y<k-i\) 的条件的点，因为只有这些点没有被当前所选的这个三角形所包含，所以需要加上这些点的代价。但是这个方程转移的时间复杂度是 \(O(n^{2})\) 的，所以还需要优化。

我们可以发现一些性质，首先方程中的 \(A\times(i-j-1)\) 一定是递减的，而 \(cost\) 值的变化也有一些规律。从 \(i\) 变到 \(i+1\) 的过程中，需要加上满足 \(x=i\) 的点的代价，减去满足 \(y=k-i\) 的点的代价，其余的点不会变化。所以我们发现每一次从 \(i\) 变为 \(i+1\) 我们都可以只修改之前所有 \(A\) 和 \(cost\) 的值就行了，每一次的值就是前面所有数的最小值，而这两个操作都可以用线段树来维护，时间复杂度 \(O(n \log n)\)。注意线段树维护的每一个 \(j\) 的值已经是 \(dp_{j}+(i-j-1)\times A+cost\) 了，所以直接查询最小值就可以了。

注意因为坐标轴的最小值为 \(0\)，所以我们还需要维护一个下标为 \(-1\) 的值，这个值代表前面还什么都没有选时的代价。

Code

#include<bits/stdc++.h>
using namespace std; 
#define int long long
#define inf 0x3f
#define inf_db 127
#define ls id << 1
#define rs id << 1 | 1
#define re register
#define endl '\n'
typedef pair <int,int> pii;
const int MAXN = 1e6 + 10;
int n,x,y,c,cost[MAXN],k,A,dp[MAXN];
struct SegmentTree{int id,l,r,mn,add;}tree[MAXN];
inline void Pushup(int id){tree[id].mn = min(tree[ls].mn,tree[rs].mn);}
inline void Build(int id,int l,int r)
{
	tree[id].l = l,tree[id].r = r;
	if(l == r){tree[id].mn = 0;return;}
	int mid = (l + r) >> 1;
	Build(ls,l,mid),Build(rs,mid + 1,r);
}
inline void Pushdown(int id)
{
	if(tree[id].add == 0) return;
	tree[ls].mn += tree[id].add,tree[ls].add += tree[id].add;
	tree[rs].mn += tree[id].add,tree[rs].add += tree[id].add;
	tree[id].add = 0;
}
inline void Add(int id,int l,int r,int a,int b,int c)
{
	if(a <= l && b >= r)
	{
		tree[id].mn += c;
		tree[id].add += c;
		return;
	}
	Pushdown(id);
	int mid = (l + r) >> 1;
	if(a <= mid) Add(ls,l,mid,a,b,c);
	if(b > mid) Add(rs,mid + 1,r,a,b,c);
	Pushup(id);
}
inline int Query(int id,int l,int r,int a,int b)
{
	if(a <= l && b >= r) return tree[id].mn;
	Pushdown(id);
	int mid = (l + r) >> 1,res = 1e18;
	if(a <= mid) res = min(res,Query(ls,l,mid,a,b));
	if(b > mid) res = min(res,Query(rs,mid + 1,r,a,b));
	return res;
}
std::vector <pii> a[MAXN];
signed main()
{
	cin >> n >> k >> A;
	Build(1,-1,k);
	for(int i = 1;i <= n;i++)
	{
		cin >> x >> y >> c;
		a[y].emplace_back(x,c);
		if(x + y != k) cost[x] += c;
	}
	for(int i = 0;i <= k;i++)
	{
		for(int j = 0;j < a[k - i].size();j++) Add(1,-1,k,-1,a[k - i][j].first - 1,-a[k - i][j].second);
		Add(1,-1,k,-1,i - 1,cost[i]);
		if(i != 0) Add(1,-1,k,-1,i - 2,A);
		dp[i] = Query(1,-1,k,-1,i - 1),Add(1,-1,k,i,i,dp[i]);
	}
	cout << dp[k]; 
	return 0;
}