AT_s8pc_5_f Lunch Menu

roger_yrj · 2024-11-25 20:58:41 · 题解

题意

给你一个 N 个数的数组 a，Q 个区间和一个整数 M。你最多能选 M 个 a 的数使它变成 0，求 \sum\limits_{i=1}^Q\max\limits_{j=l_i}^{r_i}a_j 的最小值。

题解

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

当一个数保留时，我们可以立即处理跨过这个点的所有区间。那么就能将一个大问题分解成两个小问题。

比如当我们处理 [l,r] 中的问题时，保留这个区间中最大的数 x，位置为 y。那么就能分解为两个子问题：处理 [l,y-1] 和 [y+1,r]，只能保留 [1,x-1] 的数。

维护一下上一次保留哪个数和还剩几次操作次数，然后记忆化搜索即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=55;
int n,m,q,a[N],cnt[N][N][N],b[N];
ll f[N][N][N][N];
ll dfs(int l,int r,int x,int y){
    if(y>=r-l+1||l>r)return 0;
    if(~f[l][r][x][y])return f[l][r][x][y];
    int t=x;
    while(t<=n&&(b[t]<l||r<b[t]))t++;
    if(t>n)return 0;
    f[l][r][x][y]=1e18;
    //save
    for(int i=0;i<=y;i++)f[l][r][x][y]=min(f[l][r][x][y],dfs(l,b[t]-1,x,i)+dfs(b[t]+1,r,x,y-i)+1ll*cnt[b[t]][l][r]*a[b[t]]);
    //delete
    if(y)f[l][r][x][y]=min(f[l][r][x][y],dfs(l,r,t+1,y-1));
    return f[l][r][x][y];
}
bool cmp(int x,int y){return a[x]>a[y];}
int main(){
    memset(f,-1,sizeof(f));
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=i;
    sort(b+1,b+n+1,cmp);
    for(int i=1,l,r;i<=q;i++){
        scanf("%d%d",&l,&r);
        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]++;
                }
            }
        }
    }
    cout<<dfs(1,n,1,m);
}