1 条题解

  • 2
    @ 2026-10-27 12:37:25

    感觉这个题难点完全在于往这方面想..

    考虑已知 pp 的情况下这个值可以怎么求。

    首先可以贪心地对其排序,按值从大到小考虑。

    然后就能得到特别多的假贪心做法。

    这时候可以考虑,有没有别的办法求它。

    答案是类似最小值的和的形式,所以可以尝试用序列分治来解决。

    对于一个区间,我们找它的最小值,处理横跨最小值的答案,然后递归左右区间。

    于是,对于原问题,我们能够通过区间 dp 来做。

    具体地,设 dpl,r,xdp_{l,r,x} 表示只考虑被完全包含于区间 [l,r][l,r] 的人,区间 [l,r][l,r] 内价格最小值为 xx 的最优答案。

    转移前缀和优化一下就做完了。

    复杂度 O(n3m)O(n^3m)。注意转移时要先枚举断点再枚举 xx,否则会退化为 O(n3m2)O(n^3m^2)。

    #include<bits/stdc++.h>
    using namespace std;
    //#define int long long
    #define lb(x) x&(-x)
    #define ls(p) (p<<1)
    #define rs(p) ((p<<1)|1)
    #define pii pair<int,int>
    #define F first
    #define S second
    #define mkp make_pair 
    #define psb push_back
    #define vi vector<int>
    const int mod=998244353;
    const int N=4040,inf=2e9+10;
    int n,m;
    int L[N],R[N],C[N];
    vector<pii >hum[N],humr[N];
    int dp[55][55][N],sum[55][55][N];
    int rem[55][55][N],rsum[55][55][N];
    int b[N],btt;
    int EF(int x){
    	int l=1,r=btt;
    	while(l<r){
    		int mid=((l+r+1)>>1);
    		if(b[mid]>x) r=mid-1;
    		else l=mid;
    	}return l;
    }
    int a[N];
    int dep=0;
    void solve(int l,int r,int x){
    	if(l>r) return ;
    	a[rem[l][r][x]]=b[x];
    	int R=rem[l][r][x]-1,L=rem[l][r][x]+1;
    	solve(l,R,rsum[l][R][x]);
    	solve(L,r,rsum[L][r][x]);
    }
    int cnt[N];
    signed main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    //	system("fc ex.out my.out");return 0;
    //	freopen("ex.in","r",stdin);
    //	freopen("my.out","w",stdout);
    	cin>>n>>m;
    	for(int i=1;i<=m;i++){
    		cin>>L[i]>>R[i]>>C[i];
    		b[++btt]=C[i];
    	}sort(b+1,b+btt+1);btt=unique(b+1,b+btt+1)-b-1;
    	for(int i=1;i<=m;i++){
    		C[i]=EF(C[i]);
    		hum[L[i]].psb(mkp(R[i],C[i]));
    		humr[R[i]].psb(mkp(L[i],C[i]));
    	}
    	for(int len=1;len<=n;len++){
    		for(int l=1;l+len-1<=n;l++){
    			int r=l+len-1;
    			for(int x=1;x<=btt;x++) rem[l][r][x]=l;
    			for(int k=l;k<=r;k++){
    				for(pii p:hum[k])
    					if(p.F<=r) cnt[p.S]++;
    				int nwcnt=0;
    				for(int x=btt;x>=1;x--){
    					nwcnt+=cnt[x];
    					int val=sum[l][k-1][x]+sum[k+1][r][x]+nwcnt*b[x];
    					if(val>dp[l][r][x]) rem[l][r][x]=k;
    					dp[l][r][x]=max(dp[l][r][x],val);	
    				}
    				for(pii p:humr[k])
    					if(p.F>=l) cnt[p.S]--;
    			}
    			sum[l][r][btt+1]=-1;
    			for(int x=btt;x>=1;x--){
    				if(dp[l][r][x]>sum[l][r][x+1]){
    					rsum[l][r][x]=x;
    				}else rsum[l][r][x]=rsum[l][r][x+1];
    				sum[l][r][x]=max(sum[l][r][x+1],dp[l][r][x]);
    			}
    		}
    	}
    	cout<<sum[1][n][1]<<"\n";
    	solve(1,n,rsum[1][n][1]);
    	for(int i=1;i<=n;i++){
    		cout<<a[i]<<" ";
    	}
    	return 0;
    } 
    /*
    */
    

    信息

    ID
    948
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    76
    已通过
    8
    上传者