专栏文章

AT_s8pc_5_f Lunch Menu

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqzvdvl
此快照首次捕获于
2025/12/04 13:27
3 个月前
此快照最后确认于
2025/12/04 13:27
3 个月前
查看原文

题意

给你一个 NN 个数的数组 aa，QQ 个区间和一个整数 MM。你最多能选 MM 个 aa 的数使它变成 00，求 ∑i=1Qmax⁡j=liriaj\sum\limits_{i=1}^Q\max\limits_{j=l_i}^{r_i}a_j 的最小值。

题解

对于每个区间，我们只关注最大值，所以我们从大到小考虑每一个数是否变 00。
当一个数保留时，我们可以立即处理跨过这个点的所有区间。那么就能将一个大问题分解成两个小问题。
比如当我们处理 [l,r][l,r] 中的问题时，保留这个区间中最大的数 xx，位置为 yy。那么就能分解为两个子问题：处理 [l,y−1][l,y-1] 和 [y+1,r][y+1,r]，只能保留 [1,x−1][1,x-1] 的数。
维护一下上一次保留哪个数和还剩几次操作次数，然后记忆化搜索即可。
CPP
#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);
}

评论

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

正在加载评论...