专栏文章

CF1146G Zoning Restrictions

rroger_yrj
CF1146G题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqzwl0i
此快照首次捕获于
2025/12/04 13:28
3 个月前
此快照最后确认于
2025/12/04 13:28
3 个月前
查看原文
对于每个区间，我们只关注最大值，所以我们考虑从大到小填数。
当我们填了一个数时，由于是从大到小填，所以可以立刻处理所有跨过这个点的区间。那么此时就能将问题分裂为两个子问题。
举个例子：当我们处理 [l,r][l,r] 中的问题时，当我们在位置 xx 填了一个数 yy，那么就能分裂为两个子问题：[l,x−1][l,x-1] 中填 [0,y][0,y]，[x+1,r][x+1,r] 中填 [0,y][0,y]。
记忆化搜索即可，时间复杂度 O(n3h(h+m))O(n^3h(h+m))。
CPP
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define A first
#define B second
using namespace std;
const int N=55;
int n,q,a[N],b[N],H;
ll f[N][N][N];
vector<pii>cnt[N][N][N];
ll dfs(int l,int r,int x){
	if(l>r)return 0;
	if(~f[l][r][x])return f[l][r][x];
	f[l][r][x]=0;
	for(int i=l;i<=r;i++){
		array<int,55>vis;
		for(int j=0;j<=x;j++)vis[j]=0;
		for(pii j:cnt[i][l][r])vis[j.A+1]+=j.B;
		for(int j=1;j<=x;j++)vis[j]+=vis[j-1];
		for(int j=0;j<=x;j++)f[l][r][x]=max(f[l][r][x],dfs(l,i-1,j)+dfs(i+1,r,j)+j*j-vis[j]);
	}
	return f[l][r][x];
}
int main(){
	memset(f,-1,sizeof(f));
	cin>>n>>H>>q;
	for(int i=1,l,r,x,c;i<=q;i++){
		scanf("%d%d%d%d",&l,&r,&x,&c);
		for(int j=l;j<=r;j++){
			for(int L=1;L<=l;L++){
				for(int R=r;R<=n;R++){
					cnt[j][L][R].push_back(mp(x,c));
				}
			}
		}
	}
	cout<<dfs(1,n,H);
}

评论

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

正在加载评论...