专栏文章

题解：P12196 [NOISG 2025 Prelim] Lasers 2

___FL__
P12196题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miokpt7e
此快照首次捕获于
2025/12/02 20:47
3 个月前
此快照最后确认于
2025/12/02 20:47
3 个月前
查看原文

Solution

显然当其他墙解锁后可以移动到最长的墙后面，所以我们考虑最长的墙的位置。
不妨设 fi,jf_{i,j} 表示对于前 ii 列，未被阻挡的激光为 jj 束时的最小代价（钦定第 ii 列未被阻挡），显然有转移：
fi,j=min⁡k<ifk,j−1+w(k,i)f_{i,j}=\min_{k<i} f_{k,j-1}+w(k,i)
其中，w(k,i)w(k,i) 表示解锁阻挡第 ii 列但不阻挡第 kk 列的墙的花费（因为阻挡第 kk 列的已经算过了）。显然线段树容易处理这个问题，枚举到第 ii 列时，修改左端点为 ii 的墙并还原右端点为 ii 的墙，同时加入 fi,j−1f_{i,j-1}。具体可见代码。
对 ff 取前缀最大值，使其一般化；同理求得后缀 gi,jg_{i,j} 表示第 ii 到第 ww 列，未被阻挡的激光为 jj 束时的最小代价。
枚举最长墙的位置。枚举左边未被阻挡的激光数量，二分右边最多可以有多少激光不被遮挡，取最大值。
处理 ff 和 gg 时和处理答案时的时间复杂度都为 O(w2log⁡w)O(w^2\log w)，可以通过。

Code

（代码中 f,gf,g 的含义与上文不同）
CPP
#include <bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
const int N = 2005;
int h,w,k,f[N][N],p[N<<2],g[N<<2],y[N][N];
struct node
{
	int l,r,c;
}a[N],b[N];
bool cmp(node a,node b)
{
	return a.l < b.l;
}
void pushdown(int root)
{
	p[root*2] += g[root];
	p[root*2+1] += g[root];
	g[root*2] += g[root];
	g[root*2+1] += g[root];
	g[root] = 0;
}
void update(int root,int l,int r,int ql,int qr,int x)
{
	if (ql <= l && qr >= r)
	{
		p[root] += x;
		g[root] += x;
		return;
	}
	if (g[root]) pushdown(root);
	int mid = (l+r)/2;
	if (qr <= mid) update(root*2,l,mid,ql,qr,x);
	else if (ql > mid) update(root*2+1,mid+1,r,ql,qr,x);
	else update(root*2,l,mid,ql,mid,x),update(root*2+1,mid+1,r,mid+1,qr,x);
	p[root] = min(p[root*2],p[root*2+1]);
}
int query(int root,int l,int r,int ql,int qr)
{
	if (ql <= l && qr >= r) return p[root];
	if (g[root]) pushdown(root);
	int mid = (l+r)/2;
	if (qr <= mid) return query(root*2,l,mid,ql,qr);
	if (ql > mid) return query(root*2+1,mid+1,r,ql,qr);
	return min(query(root*2,l,mid,ql,mid),query(root*2+1,mid+1,r,mid+1,qr));
}
signed main()
{
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> h >> w >> k;
	int mxl,mxp = 0,mxc,mxk;
	for (int i = 1; i <= h; i++)
	{
		cin >> a[i].l >> a[i].r >> a[i].c;
		if (a[i].r-a[i].l+1 > mxp) mxp = a[i].r-a[i].l+1,mxl = a[i].l,mxc = a[i].c,mxk = i;
	}
	a[mxk].l = 99999999;
	sort(a+1,a+h+1,cmp);
	h--;
	for (int i = 1; i <= h; i++)
		b[i] = {a[i].r,a[i].l,a[i].c};
	sort(b+1,b+h+1,cmp);
	memset(f,0x3f,sizeof f);
	for (int i = 0; i <= w; i++)
		f[i][0] = 0;
	memset(y,0x3f,sizeof y);
	for (int i = 0; i <= w; i++)
		y[i][0] = 0;
	for (int i = 1; i <= w; i++)
	{
		int pot1 = 1,pot2 = 1,tot = 0;
		memset(p,0,sizeof p);
		memset(g,0,sizeof g);
		for (int j = 1; j <= w; j++)
		{
			while (pot1 <= h && a[pot1].l == j) update(1,1,w,a[pot1].l,a[pot1].r,-a[pot1].c),tot += a[pot1].c,pot1++;
			if (j >= i)
			{
				if (i == 1) f[j][i] = tot;
				else f[j][i] = query(1,1,w,1,j-1)+tot;
			}
			update(1,1,w,j,j,f[j][i-1]);
			while (pot2 <= h && b[pot2].l == j) update(1,1,w,b[pot2].r,b[pot2].l,b[pot2].c),tot -= b[pot2].c,pot2++;
		}
	}
	for (int i = 1; i <= w; i++)
	{
		int pot1 = h,pot2 = h,tot = 0;
		memset(p,0,sizeof p);
		memset(g,0,sizeof g);
		for (int j = w; j >= 1; j--)
		{
			while (pot2 >= 1 && b[pot2].l == j) update(1,1,w,b[pot2].r,b[pot2].l,-b[pot2].c),tot += b[pot2].c,pot2--;
			if (j <= w-i+1)
			{
				if (i == 1) y[j][i] = tot;
				else y[j][i] = query(1,1,w,j+1,w)+tot;
			}
			update(1,1,w,j,j,y[j][i-1]);
			while (pot1 >= 1 && a[pot1].l == j) update(1,1,w,a[pot1].l,a[pot1].r,a[pot1].c),tot -= a[pot1].c,pot1--;
		}
	}
	for (int i = 1; i <= w; i++)
		for (int j = i+1; j <= w; j++)
			f[j][i] = min(f[j][i],f[j-1][i]);
	for (int i = 1; i <= w; i++)
		for (int j = w-i; j >= 1; j--)
			y[j][i] = min(y[j][i],y[j+1][i]);
	int ans = 0;
	for (int i = 1; i <= w; i++)
	{
		int bl = i,br = i+mxp-1;
		if (br > w) break;
		int e = k;
		if (bl != mxl) e -= mxc;
		if (e < 0) continue;
		for (int j = 0; j < bl; j++)
		{
			int c = e-f[bl-1][j];
			if (c < 0) continue;
			int l = 0,r = w-br;
			while (l+1 < r)
			{
				int mid = (l+r)/2;
				if (y[br+1][mid] <= c) l = mid;
				else r = mid-1;
			}
			if (y[br+1][r] <= c) ans = max(ans,j+r);
			else ans = max(ans,j+l);
		}
	}
	cout << ans;
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...