BZOJ4583 : 购物

首先，如果一家店的区间完全包含了另一家，那么可以删掉另一家，中间的可以用组合数计算方案数。

那么现在将所有店按$l$排序，那么$l$和$r$都严格递增。

设$f[i][j][k]$表示当前是第$i$天的开端，当前这家店还要卖$j$个红球，$k$个绿球的方案数。

还需要卖多少蓝球可以通过天数与$j,k$的差值得出，所以不需要记录。

如果这一天是某两家店重合的第一天，那么重合部分可以通过组合数计算方案数，然后直接跳到不重合的第一天。

其它情况都可以枚举方案暴力转移。

时间复杂度$O(TV^2)$。

#include<cstdio>

#include<algorithm>

const int N=55,T=505,V=105,P=1000000007;

int n,i,j,k,x,len,flag,del[N],v[T],id[T],C[T][T],f[T][V][V],ans;

struct E{int st,en,r,g,b;}a[N];

inline bool cmp(const E&a,const E&b){return a.st<b.st;}

inline int cal(int R,int G,int B){return 1LL*C[R+G+B][R]*C[G+B][G]%P;}

inline void up(int&x,int y){x+=y;if(x>=P)x-=P;}

int main(){

  scanf("%d",&n);

  for(i=1;i<=n;i++)scanf("%d",&a[i].st);

  for(i=1;i<=n;i++)scanf("%d",&a[i].r);

  for(i=1;i<=n;i++)scanf("%d",&a[i].g);

  for(i=1;i<=n;i++){

    scanf("%d",&a[i].b);

    a[i].en=a[i].st+a[i].r+a[i].g+a[i].b-1;

    for(j=a[i].st;j<=a[i].en;j++)v[j]++;

  }

  for(i=1;i<T;i++)if(v[i]>2)return puts("0"),0;

  for(f[0][0][0]=C[0][0]=i=1;i<T;i++)for(C[i][0]=j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;

  do{

    flag=0;

    for(i=1;i<=n;i++)if(!del[i])for(j=1;j<=n;j++)if(!del[j]&&i!=j){

      if(a[i].st<=a[j].st&&a[j].en<=a[i].en){

        del[j]=1;

        f[0][0][0]=1LL*f[0][0][0]*cal(a[j].r,a[j].g,a[j].b)%P;

        a[i].r-=a[j].r,a[i].g-=a[j].g,a[i].b-=a[j].b;

        len=a[j].r+a[j].g+a[j].b;

        if(a[i].r<0||a[i].g<0||a[i].b<0)return puts("0"),0;

        if(a[i].r==0&&a[i].g==0&&a[i].b==0)del[i]=1;

        a[i].en-=len;

        for(k=1;k<=n;k++)if(!del[k]&&k!=i)if(a[k].st>a[j].en)a[k].st-=len,a[k].en-=len;

        flag=1;

        break;

      }

    }

  }while(flag);

  for(j=0,i=1;i<=n;i++)if(!del[i])a[++j]=a[i];

  n=j;

  std::sort(a+1,a+n+1,cmp);

  for(i=1;i<T;i++)v[i]=0;

  for(i=1;i<=n;i++)for(j=a[i].st;j<=a[i].en;j++)id[j]=i,v[j]++;

  for(i=0;i<502;i++)for(j=0;j<V;j++)for(k=0;k<V;k++)if(f[i][j][k]){

    if(!v[i])up(f[i+1][a[id[i+1]].r][a[id[i+1]].g],f[i][j][k]);

    else if(v[i]==1){

      if(i==a[id[i]].en)up(f[i+1][a[id[i+1]].r][a[id[i+1]].g],f[i][j][k]);

      else{

        if(j)up(f[i+1][j-1][k],f[i][j][k]);

        if(k)up(f[i+1][j][k-1],f[i][j][k]);

        if(a[id[i]].en+1-i-j-k)up(f[i+1][j][k],f[i][j][k]);

      }

    }else if(v[i]==2){

      x=a[id[i-1]].en+1-i-j-k;

      if(j>a[id[i]].r||k>a[id[i]].g||x>a[id[i]].b)continue;

      up(f[a[id[i-1]].en+1][a[id[i]].r-j][a[id[i]].g-k],1LL*f[i][j][k]*cal(j,k,x)%P);

    }

  }

  return printf("%d",f[i][0][0]),0;

}