CF1146G Zoning Restrictions

roger_yrj · 2024-11-25 20:36:37 · 题解

对于每个区间，我们只关注最大值，所以我们考虑从大到小填数。

当我们填了一个数时，由于是从大到小填，所以可以立刻处理所有跨过这个点的区间。那么此时就能将问题分裂为两个子问题。

举个例子：当我们处理 [l,r] 中的问题时，当我们在位置 x 填了一个数 y，那么就能分裂为两个子问题：[l,x-1] 中填 [0,y]，[x+1,r] 中填 [0,y]。

记忆化搜索即可，时间复杂度 O(n^3h(h+m))。

#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);
}