首页 > 代码库 > BZOJ4583 : 购物
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;}
BZOJ4583 : 购物
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。