【神仙DP】【单调队列】【模拟题】区间覆盖

时间:2022-10-06 14:55:44

传送门

Description

给出数轴上的n个线段,保留最多k条线段,问这些被保留下来的线段的并集长度为最多为多少。

Input

第一行两个数n和k

接下来n行,每行两个数,表示一条线段的左右端点。(0<=每个数<109

Output

一个数表示答案。

Sample Input


Sample Output


Hint

对于30%的数据,1<=n<=20

对于60%的数据,1<=n<=300

对于100%的数据,1<=n<=100000,,1<=k<=min(100,n);

Solution

  想了半天,看这个数据范围大概是nlogn可过,n*k也可过。先考虑贪心,貌似可行,但是贪心的复杂的是O(kn2logn)……手动再见还不如朴素DP。

   考虑DP。朴素DP十分好想,按区间右端点排序,设f[i][j]为前i个线段选j个,其中必选i。这样易得转移方程:

        f[i][j]=max(max{f[h][j-1]+r[i]-l[i]|l[i]>=r[h]},max{f[h][j-1]+r[i]-r[h]|l[i]>=r[h]})。

   直观上,方程表示从前h个选j-1个开始转移,按区间是否有交划分转移。

   如此转移,需要枚举当前区间,当前区间前的区间,以及线段个数,时间复杂度为O(n2k)。期望得分50分。
   下面我进行了许多毫无卵用的优化:

      观察前半个转移方程,需要找到前h个中最大的f[h][j-1]。显然线段树可以保存区间最大值,于是对于前半段线段树优化。这样就无需枚举h。那么如何确定h呢?考虑因为右端点满足单调性,于是进行二分。二分h的位置。复杂度O(logn)。对于后半个方程,想破脑袋也只能枚举转移,这样在期望状态下,复杂度为O(nklog2n)。两个log一个是线段树的一个是二分的。于是我们发现,我们的期望得分仍然是50分……

   这是跑的最快的50分做法。差点卡常卡过70分。

   下面是正解:

       对于前半部分方程,需要取前i个的最大值,显然前缀最大值可做。即Max[i][j]=max(Max[i-1][j],frog[i][j])这样,对于前半部分的转移,转移时间从O(logn)降低到了O(1)。可是这样期望还是50分啊。考虑最大h的位置。由于满足右端点递增,如果在排序是将左端点为第二关键字升序排序,那么显然h是递增的。因为h代表的是右端点小于等于l[i]的右端点区间最大的编号。由于r[i]递增,l[i]升序,所以l[i]递增。(对于相互包含的区间,显然大区间优于小区间,需要去重)这样只需要不断++h,判断h是否合法即可。这样,决策时间也降到了O(1)。下面考虑对于后半部分方程的转移。由于r[i]、l[i]递增,所以满足第二部分方程的h是递增的。如此可以进行单调队列优化。对于合法的但是小的f,会被新进队列的元素直接覆盖。不合法的会从队首弹出。如此,整个转移的复杂度被降到了O(1)。所以本题的复杂度为Θ(nk+n+nlogn),其中nk为DP,n为单调队列总维护次数,nlogn为排序复杂的。即O(nk)。这样复杂度就合法通过了本题。

Code

#include<cstdio>
#include<algorithm>
#define maxn 100010 inline void qr(int &x) {
char ch=getchar();bool f=false;
while(ch>''||ch<'') {
if(ch=='-') f=true;
ch=getchar();
}
while(ch>=''&&ch<='') x=(x<<)+(x<<)+(ch^),ch=getchar();
if(f) x=-x;
} inline int max(const int &a,const int &b) {if(a>b)return a;else return b;}
inline int min(const int &a,const int &b) {if(a<b)return a;else return b;}
inline int abs(const int &x) {if(x>=) return x;else return -x;} inline void swap(int &a,int &b) {
int temp=a;a=b;b=temp;
} int n,k,ans;
struct M {
int l,r;
};
M MU[maxn];
int frog[maxn][];
inline bool cmp(const M &a,const M &b) {
if(a.r!=b.r) return a.r<b.r;
return a.l<b.l;
} int main() {
freopen("cover10.in","r",stdin);
freopen("ans.out","w",stdout);
qr(n);qr(k);
for(int i=;i<=n;++i) {
qr(MU[i].l);qr(MU[i].r);
}
std::sort(MU+,MU++n,cmp);
for(int i=;i<=n;++i) {
frog[i][]=MU[i].r-MU[i].l;
for(int j=k;j>;--j) {
for(int h=;h<i;++h) {
if(MU[h].r<=MU[i].l) frog[i][j]=max(frog[i][j],frog[h][j-]+MU[i].r-MU[i].l);
else frog[i][j]=max(frog[i][j],frog[h][j-]+MU[i].r-MU[h].r);
}
}
ans=max(ans,frog[i][k]);
}
printf("%d\n",ans);
return ;
}

50分无优化

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
ld eps=1e-;
ll pp=;
ll mo(ll a,ll pp){if(a>= && a<pp)return a;a%=pp;if(a<)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=;for(;b;b>>=,a=mo(a*a,pp))if(b&)ans=mo(ans*a,pp);return ans;}
ll read(){
ll ans=;
char last=' ',ch=getchar();
while(ch<'' || ch>'')last=ch,ch=getchar();
while(ch>='' && ch<='')ans=ans*+ch-'',ch=getchar();
if(last=='-')ans=-ans;
return ans;
}
//head
#define N 110000
ll f[][N];
pr a[N];
int n,k,nn,q[N];
ll b[N],c[N];
int main(){
freopen("cover.in","r",stdin);
freopen("cover.out","w",stdout);
n=read();k=read();
rep(i,,n)a[i].first=read(),a[i].second=read();
sort(a+,a+n+);
nn=;
rep(i,,n)
if(a[nn].second<a[i].second)a[++nn]=a[i];
n=nn;k=min(k,n);
rep(i,,)
rep(j,,n)f[i][j]=-;
f[][]=;
int ans=;
rep(i,,k-){
b[]=f[][];
rep(j,,n)b[j]=max(f[][j],b[j-]);
rep(j,,n)c[j]=f[][j]-a[j].second;
int t=,w=,z=;
rep(j,i+,n){
while(a[z+].second<=a[j].first)++z;
while(t<=w && c[j-]>=c[q[w]])--w;
q[++w]=j-;
while(t<=w && q[t]<=z)++t;
f[][j]=b[z]+a[j].second-a[j].first;
if(t<=w)f[][j]=max(f[][j],c[q[t]]+a[j].second);
ans=max((ll)ans,f[][j]);
}
rep(j,,n)f[][j]=f[][j],f[][j]=-;
} printf("%d\n",ans);
return ;
}

Summary

  1、在需要前i个元素中最大值且i转移单调时,考虑前缀最大值而不是线段树。这样复杂度可以下降为O(1)。其实我就是数据结构学傻了

  2、转移区间满足单调性时,考虑单调队列优化。需要注意的是,单调队列中单调的是元素下标而不是DP值。这不是废话吗

  3、神仙题优化时可以画图考虑转移位置,从而发现性质。