题解 P1973 【[NOI2011]NOI 嘉年华】

· · 题解

前面的话:

这道dp优化的难度并不大,但是推导比较经典,最后的优化手段也很经典,是一道练习好题!

细节有点多,不过如果认真思考方法的话可以躲掉大部分。

自以为把最后的单调性优化讲的比较清楚

题意比较复杂,简单来说吧:

给出n个区间,让你把这些区间分成两份,允许丢弃,两份区间不能有交。

第一问: 让两份中分到区间数最小的一份,尽量得到更多的区间。

第二问: 在第\forall i个区间必须不丢弃的情况下的上一问答案。

分析第一问:

活动不包含开始和结束瞬间,为了方便处理,我们吧所有的区间尾先减一,就能转化成熟悉的数组占位。

显然可以把区间都离散化,设离散化之后的时间域为[1,T]

有一个二维dp:设f[i][j]为

前i个时刻第一份选择了j(可以为0)个区间,此时第二份最多能选择多少个。

(注意要初始化成-INF,边界是f[0][0]=0)

为了方便处理,我们在离散化后时间轴上留一前一后两个空位。

转移:

先设c(l,r)指被[l,r]完全包含的区间个数。

这个东西可以大力O(n^3)预处理,方法就是判断每个区间有没有被包容在[l,r]内。

f[i][j]\leftarrow\max\limits_{k=1}^{i-1}f[k][j-c(k+1,i)] f[i][j]\leftarrow\max\limits_{k=1}^{i-1}f[k][j]+c(k+1,i)

那么答案就是\max\limits_{j=0}^{n}min(f[T][j],j)

总的复杂度是O(n^3)

分析第二问:

如何强制选择某一个区间?我们可以先把这个区间给予某一份(那一份都行,不妨给第一份),然后把剩下的东西算出来。

详细地说:

我们要设g[i][j]为

后i个时刻第一份选择了j个区间,此时第二份最多能选择多少个。

转移类似f,不再赘述。(边界是g[n+1][0]=0)

那么,强制选择了某个区间[l,r]给第二份之后,我们要枚举中间分给第一份的一整段区间(包含[l,r])

此外还要枚举第一份选择的区间数(前后都要枚举):

\max\limits_{i=1}^{l-1}\max\limits_{j=r+1}^{T}\max\limits_{k=0}^{n}\max\limits_{t=0}^{n}min(f[i][k]+g[j][t],k+t+c(i+1,j-1))

这个式子是O(n^4)的,总复杂度就是O(n^5),不能通过本题。

对于每个小区间都找一个大段来包含,我们其实做了很多重复的工作。

设s(l,r)=\max\limits_{k=0}^{n}\max\limits_{t=0}^{n}min(f[l][k]+g[r][t],k+t+c(l+1,r-1))

(注意这个区间两边开)

那么答案就变成\max\limits_{i=1}^{l-1}\max\limits_{j=r+1}^{T}s(i,j),这样子就是一次O(n^2)的了。

问题在于如何预处理s(l,r),按照上面的式子爆算复杂度高达O(n^4),但是据说加剪枝卡常能过。

先贴一个暴力Code:

由于数据过水居然AC了?看来考场上也可以使用这些面向数据编程的办法,毕竟数据不好造啊……

#include<algorithm>
#include<cstdio>
#define MaxN 205
#define INF 1000000000
using namespace std;
int n;
struct Line
{int l,r;}l[MaxN];
int xx[MaxN*2],tot;
int f[MaxN*2][MaxN],g[MaxN*2][MaxN];
int c[MaxN*2][MaxN*2],s[MaxN*2][MaxN*2];
int main()
{
  scanf("%d",&n);
  for (int i=1;i<=n;i++){
    scanf("%d%d",&l[i].l,&l[i].r);
    l[i].r+=l[i].l-1;
    xx[++tot]=l[i].l;
    xx[++tot]=l[i].r;
  }sort(xx+1,xx+tot+1);
  for (int i=1;i<=n;i++){
    l[i].l=lower_bound(xx+1,xx+tot+1,l[i].l)-xx+1;
    l[i].r=lower_bound(xx+1,xx+tot+1,l[i].r)-xx+1;
  }tot+=2;

  for (int i=1;i<=tot;i++)
    for (int j=i;j<=tot;j++)
      for (int k=1;k<=n;k++)
        if (i<=l[k].l&&l[k].r<=j)
          c[i][j]++;

  for (int i=0;i<=tot+1;i++)
    for (int j=0;j<=n;j++)
      f[i][j]=g[i][j]=-INF;
  f[0][0]=g[tot+1][0]=0;
  for (int i=1;i<=tot;i++)
    for (int j=0;j<=n;j++)
      for (int k=0,sav;k<i;k++){
        sav=c[k+1][i];
        if (j>=sav)f[i][j]=max(f[i][j],f[k][j-sav]);
        f[i][j]=max(f[i][j],f[k][j]+sav);
      }

  int ans=0;
  for (int i=0;i<=n;i++)
    ans=max(ans,min(f[tot][i],i));
  printf("%d\n",ans);

  for (int i=tot;i;i--)
    for (int j=0;j<=n;j++)
      for (int k=i+1,sav;k<=tot+1;k++){
        sav=c[i][k-1];
        if (j>=sav)g[i][j]=max(g[i][j],g[k][j-sav]);
        g[i][j]=max(g[i][j],g[k][j]+sav);
      }

  for (int i=1;i<=tot;i++)
    for (int j=i+2;j<=tot;j++){
      s[i][j]=-INF;
      for (int k=0;k<=n;k++){
        if (f[i][k]<0)break;
        for (int t=0;t+k<=n;t++){
          if (g[j][t]<0)break;
          s[i][j]=max(s[i][j],
            min(f[i][k]+g[j][t],k+t+c[i+1][j-1])
          );
        }
      }
    }

  for (int t=1;t<=n;t++){
    ans=0;
    for (int i=1;i<l[t].l;i++)
      for (int j=l[t].r+1;j<=tot;j++)
        ans=max(ans,s[i][j]);
    printf("%d\n",ans);
  }return 0;
}

再看一遍式子:

s(l,r)=\max\limits_{k=0}^{n}\max\limits_{t=0}^{n}min(f[l][k]+g[r][t],k+t+c(l+1,r-1))

我们发现这个min很烦,但是它的左右两边分别是两份的区间数,这两份的地位是一样的。

那么,对于一种分法,把两份的内容交换又能得到另一种,所以会在min中按两种顺序各出现一次。

也就是说,我们直接认为k+t+c(l+1,r-1)是较大值,按照这个规则来优化,最终不会漏掉最优解。

(前面讲了c(l+1,r-1)这个常数分给谁无所谓,那么现在规定顺序以后分给最大值肯定不会影响。)

现在的目标就是尽量让左边变大(在维持右边大的情况下)

我们发现,f[l][k]随着k的增大而减小;g[r][t]随着t的增大而减小。

那么,再k增加的时候,再令t增加显然不优,因为我们在单纯地削减左边而增加右边。

有了这个单调性,预处理的复杂度就变为了O(n^3),可以轻松通过本题。

Code:

貌似只比暴力快了一倍……

#include<algorithm>
#include<cstdio>
#define MaxN 205
#define INF 1000000000
using namespace std;
int n;
struct Line
{int l,r;}l[MaxN];
int xx[MaxN*2],tot;
int f[MaxN*2][MaxN],g[MaxN*2][MaxN];
int c[MaxN*2][MaxN*2],s[MaxN*2][MaxN*2];
int main()
{
  scanf("%d",&n);
  for (int i=1;i<=n;i++){
    scanf("%d%d",&l[i].l,&l[i].r);
    l[i].r+=l[i].l-1;
    xx[++tot]=l[i].l;
    xx[++tot]=l[i].r;
  }sort(xx+1,xx+tot+1);
  for (int i=1;i<=n;i++){
    l[i].l=lower_bound(xx+1,xx+tot+1,l[i].l)-xx+1;
    l[i].r=lower_bound(xx+1,xx+tot+1,l[i].r)-xx+1;
  }tot+=2;

  for (int i=1;i<=tot;i++)
    for (int j=i;j<=tot;j++)
      for (int k=1;k<=n;k++)
        if (i<=l[k].l&&l[k].r<=j)
          c[i][j]++;

  for (int i=0;i<=tot+1;i++)
    for (int j=0;j<=n;j++)
      f[i][j]=g[i][j]=-INF;
  f[0][0]=g[tot+1][0]=0;
  for (int i=1;i<=tot;i++)
    for (int j=0;j<=n;j++)
      for (int k=0,sav;k<i;k++){
        sav=c[k+1][i];
        if (j>=sav)f[i][j]=max(f[i][j],f[k][j-sav]);
        f[i][j]=max(f[i][j],f[k][j]+sav);
      }

  int ans=0;
  for (int i=0;i<=n;i++)
    ans=max(ans,min(f[tot][i],i));
  printf("%d\n",ans);

  for (int i=tot;i;i--)
    for (int j=0;j<=n;j++)
      for (int k=i+1,sav;k<=tot+1;k++){
        sav=c[i][k-1];
        if (j>=sav)g[i][j]=max(g[i][j],g[k][j-sav]);
        g[i][j]=max(g[i][j],g[k][j]+sav);
      }

  for (int i=1;i<=tot;i++)
    for (int j=i+2;j<=tot;j++){
      s[i][j]=-INF;
      for (int k=0,sav,t=n;k<=n;k++){
        if (f[i][k]<0)break;
        while(t>=0){
          sav=min(f[i][k]+g[j][t],k+t+c[i+1][j-1]);
          if (sav>=s[i][j])s[i][j]=sav;
          else break;
          t--;
        }t++;
      }
    }

  for (int t=1;t<=n;t++){
    ans=0;
    for (int i=1;i<l[t].l;i++)
      for (int j=l[t].r+1;j<=tot;j++)
        ans=max(ans,s[i][j]);
    printf("%d\n",ans);
  }return 0;
}