标题

思路

解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

#include<bits/stdc++.h> using namespace std; struct Segment{int l,r,v;long long w;}a[200005],b[5005]; int n,m,k,ans,cnt,ri[5005],pre[5005],sumv[200005],p[400005],dp[5005][5005]; long long sumw[200005]; bool cmp(const Segment &x,const Segment &y){return x.l<y.l;} int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m>>k; for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r>>a[i].w; for(int i=1;i<=m;i++) cin>>b[i].l>>b[i].r; sort(a+1,a+n+1,cmp),sort(b+1,b+m+1,cmp); for(int i=1;i<=n;i++){ a[i].v=a[i].r-a[i].l+1; sumw[i]=sumw[i-1]+a[i].w; sumv[i]=sumv[i-1]+a[i].v; p[i2-1]=a[i].l,p[i2]=a[i].r; } for(int i=1;i<=m;i++){ if(b[i].l>a[n].r||b[i].r<a[1].l) continue; int l=lower_bound(p+1,p+n2+1,b[i].l)-p; int r=upper_bound(p+1,p+n2+1,b[i].r)-p-1; if(l%21&&p[l]>b[i].r||r%20&&p[r]<b[i].l) continue; l=(l+1)/2,r=(r+1)/2,ri[i]=r; for(int j=1;j<=i-1;j++) if(ri[j]<l) pre[i]=j; b[i].w=sumw[r]-sumw[l-1]; if(l!=r){ b[i].v=sumv[r]-sumv[l-1]-a[r].v-a[l].v; b[i].v+=min(b[i].r,a[l].r)-max(b[i].l,a[l].l)+1; b[i].v+=min(b[i].r,a[r].r)-max(b[i].l,a[r].l)+1; } else b[i].v=min(b[i].r,a[l].r)-max(b[i].l,a[l].l)+1; } for(int i=1;i<=m;i++){ for(int j=1;j<=k;j++) dp[i][j]=dp[i-1][j]; for(int j=k;j>=b[i].w;j--){ dp[i][j]=max(dp[i][j],dp[pre[i]][j-b[i].w]+b[i].v); ans=max(ans,dp[i][j]); } } cout<<ans<<'\n'; return 0; }