bzoj 4583 购物

4583: 购物

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 32  Solved: 16
[Submit][Status][Discuss]

Description

商店出售3种颜色的球，分别为红、绿、蓝。城市里有n个商店，第i个商店在第First_i天开始营业，连续营业Red_

i+Green_i+Blue_i天，每个商店每天只能出售一种颜色的球。每天最多有两个商店同时营业。如果同一天内有两个

商店同时营业，那么这两个商店必须出售相同颜色的球。求不同的出售方案数（对1,000,000,007取模）。两种方

案不同，当且仅当某一天某一个商店出售的球的颜色不同。

 

Input

第一行只包含一个整数n，表示商店的个数。

接下来一行有n个数，第i个数表示First_i。

接下来一行有n个数，第i个数表示Red_i。

接下来一行有n个数，第i个数表示Green_i。

接下来一行有n个数，第i个数表示Blue_i。

1≤n≤50

1≤First_i≤500

0≤Red_i, Green_i, Blue_i≤100

0<Red_i + Green_i + Blue_i

First_i + Red_i + Green_i + Blue_i - 1≤500

保证每天最多有两个商店同时营业。

 

Output

输出仅包含一个数，表示对1,000,000,007取模后的方案数。

 

 

首先想到dp，f[i][j][k]表示当前第i天，当前的商店已经卖了j个红气球，k个绿气球，这样用蓝气球的个数也是可以知道的。要是有两个区间包含的情况，则可以直接乘组合数转移。相当于被包含的区间强行放满。前后两个区间有交叉同理，因为由当前的状态可以知道接下来交叉的区间要卖红、绿、蓝气球各多少个，所以就可以直接乘组合数转移。其他情况直接转移。

 

感觉代码写的很丑，注意排序前后的顺序不同，不要搞混

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mod 1000000007
#define maxn 120

typedef long long ll;
struct node{
    int l,r,rd,bl,gr;
    bool operator < (node a)const{
        return l < a.l;
    }
}dt[maxn],dt2[maxn];
ll f[maxn * 10][maxn][maxn],fac[520],inv[520],ans;
int n,m,tag[maxn],tot,cov[maxn * 10],bl[maxn * 10];
int R[maxn],B[maxn],G[maxn],mxR,mxB,mxG,R2[maxn],B2[maxn],G2[maxn];

inline ll power(ll x,int y){
    ll res = 1;
    while ( y ){
        if ( y & 1 ) res = res * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return res % mod;
}
void init(){
    fac[0] = inv[0] = 1;
    for (int i = 1 ; i <= 500 ; i++) fac[i] = (ll)i * fac[i - 1] % mod , inv[i] = power(fac[i],mod - 2);
    for (int i = 1 ; i <= n ; i++) dt[i].rd = R[i] , dt[i].gr = G[i] , dt[i].bl = B[i];
    sort(dt + 1,dt + n + 1);
    for (int i = 1 ; i <= n ; i++) R[i] = dt[i].rd  , G[i] = dt[i].gr , B[i] = dt[i].bl;
    for (int i = 1 ; i <= n ; i++){
        for (int j = 1 ; j <= n ; j++){
            if ( j == i ) continue;
            if ( dt[i].l <= dt[j].l && dt[i].r >= dt[j].r ) tag[j] = 1;
        }
    }
    for (int i = 1 ; i <= m ; i++){
        for (int j = 1 ; j <= n ; j++){
            if ( tag[j] ) continue;
            if ( dt[j].l <= i && dt[j].r >= i ) cov[i]++;
            if ( dt[j].l > i ) break;
        }
    }
    for (int i = 1 ; i <= n ; i++){
        if ( tag[i] ){
            bl[dt[i].l] = i;
        }
    }
}
void Dodp(){
    int cur = 1;
    while ( tag[cur] ) cur++;
    f[0][0][0] = 1;    
    for (int i = 1 ; i <= m ; i++){
        if ( !cov[i] ){
            if ( !cov[i - 1] ) f[i][0][0] = f[i - 1][0][0];
            else{
                for (int j = 0 ; j <= R[cur] ; j++){
                    for (int k = 0 ; k <= G[cur] ; k++){
                        f[i][0][0] = (f[i][0][0] + f[i - 1][j][k]) % mod;
                    }
                }
            }
            continue;
        }
        if ( i > dt[cur].r ){
            for (int j = 0 ; j <= R[cur] ; j++){
                for (int k = 0 ; k <= G[cur] ; k++){
                    f[i][0][0] = (f[i][0][0] + f[i - 1][j][k]) % mod;
                }
            }
            f[i - 1][0][0] = f[i][0][0] , f[i][0][0] = 0;
            cur++;
            while ( tag[cur] ) cur++;
        }
        if ( cov[i] == 2 ){
            int jump = dt[cur].r;
            for (int j = 0 ; j <= R[cur] ; j++){
                for (int k = 0 ; k <= G[cur] && j + k <= i - dt[cur].l ; k++){
                    int r = R[cur] - j , g = G[cur] - k , b = B[cur] - (i - dt[cur].l - j - k);
                    if ( b < 0 || r + g + b < jump - i + 1 ) continue;
                    f[jump][r][g] = (f[jump][r][g] + fac[jump - i + 1] * inv[r] % mod * inv[g] % mod * inv[b] % mod * f[i - 1][j][k]) % mod;
                }
            }
            cur++ , i = jump;
            while ( tag[cur] ) cur++;
        }
        else{
            if ( bl[i] ){
                int jump = dt[bl[i]].r;
                for (int j = 0 ; j <= R[cur] ; j++){
                    for (int k = 0 ; k <= G[cur] && j + k <= i - dt[cur].l ; k++){
                        int r = R[bl[i]] + j , g = G[bl[i]] + k , b = B[bl[i]] + (i - dt[cur].l - j - k);
                        if ( r > R[cur] || g > G[cur] || b > B[cur] ) continue;
                        f[jump][r][g] = (f[jump][r][g] + fac[jump - i + 1] * inv[R[bl[i]]] % mod * inv[G[bl[i]]] % mod * inv[B[bl[i]]] % mod * f[i - 1][j][k]) % mod;
                    }
                }
                i = jump;
                continue;
            }
            for (int j = 0 ; j <= R[cur] ; j++){
                for (int k = 0 ; k <= G[cur] && j + k <= i - dt[cur].l + 1 ; k++){
                    int b = i - dt[cur].l + 1 - j - k;
                    if ( b > B[cur] ) continue;
                    if ( j > 0 ) f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][k]) % mod;
                    if ( k > 0 ) f[i][j][k] = (f[i][j][k] + f[i - 1][j][k - 1]) % mod;
                    if ( b > 0 ) f[i][j][k] = (f[i][j][k] + f[i - 1][j][k]) % mod;
                }
            }
        }    
    }
}
int main(){
//    freopen("input.txt","r",stdin);
    scanf("%d",&n);
    for (int i = 1 ; i <= n ; i++) scanf("%d",&dt[i].l);
    for (int i = 1 ; i <= n ; i++) scanf("%d",&R[i]) , mxR = max(mxR,R[i]);
    for (int i = 1 ; i <= n ; i++) scanf("%d",&G[i]) , mxG = max(mxG,G[i]);
    for (int i = 1 ; i <= n ; i++) scanf("%d",&B[i]) , mxB = max(mxB,B[i]);
    for (int i = 1 ; i <= n ; i++) dt[i].r = dt[i].l + R[i] + G[i] + B[i] - 1 , m = max(m,dt[i].r);
    init();
    Dodp();
    for (int j = 0 ; j <= 100 ; j++) 
        for (int k = 0 ; k <= 100 ; k++)
            ans = (ans + f[m][j][k]) % mod;
    printf("%lld
",ans);
    return 0;
}