1 条题解
-
2
感觉这个题难点完全在于往这方面想..
考虑已知 的情况下这个值可以怎么求。
首先可以贪心地对其排序,按值从大到小考虑。
然后就能得到特别多的假贪心做法。
这时候可以考虑,有没有别的办法求它。
答案是类似最小值的和的形式,所以可以尝试用序列分治来解决。
对于一个区间,我们找它的最小值,处理横跨最小值的答案,然后递归左右区间。
于是,对于原问题,我们能够通过区间 dp 来做。
具体地,设 表示只考虑被完全包含于区间 的人,区间 内价格最小值为 的最优答案。
转移前缀和优化一下就做完了。
复杂度 。注意转移时要先枚举断点再枚举 ,否则会退化为 。
#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; } /* */
- 1
信息
- ID
- 948
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 76
- 已通过
- 8
- 上传者