题解 P6731 【[WC2020] 选课】

· · 题解

这个题实际上是个NOIP难度的题,不过出题人放到了WC的T3,题面看起来很劝退,代码也难写,数据范围也出锅了,所以没什么人过.

为了方便描述,

令L=\max(T-\sum\limits_{i=1}^m s_i,0),即满足每类学科达到条件的情况下额外需要的学分,数据范围保证了0\leq L\leq 40.

令P为所有的限制涉及到的课程总数,数据范围保证了0\leq P\leq 12.

subtask1 : P=0

对于每类课程,相当于我们要对一些体积为1,2,3的物品做背包,查询体积为s_i,s_i+1,s_i+2,...s_i+L的最小价值,最后跑一个O(M*L^2)的背包合并.

那么我们直接跑背包就可以以O(N^2)的复杂度解决,但是太慢了.

如果体积只有1,我们可以直接排序贪心.

如果体积只有\{1,2\},那么我们按照奇偶性分类排序贪心即可,具体的实现见下文.

上述贪心可以O(n\log n)的复杂度预处理并O(1)查询某个体积的结果.

然后体积集合变成了\{1,2,3\},我们就枚举3的使用次数,然后查询对\{1,2\}的贪心结果即可.

那么我们就可以以O( 查询体积 )的复杂度回答一个单点询问.

贪心计算的复杂度为O(N\log N+NL),总复杂度O(N\log N+NL+M\times L^2),

subtask2: P\leq 12

对于限制没有涉及到的情况,把需要的解都贪心计算出并记录下来,并把限制没有涉及到的类别的dp数组先计算出来,复杂度O(N\log N+NL+M\times L^2)

剩下的还没确定的类别有O(P)个,把这O(P)个类别除去限制涉及到的部分拿出来贪心并记录答案.

O(2^P)$枚举限制涉及到的课程的选取情况$,$然后对每个情况$,$合并$O(P)$个$DP$数组即可$,$复杂度$O(2^PPL^2)

总复杂度O(N\log N+NL+M\times L^2+2^PPL^2)

代码 :

inline void upd(int &x,int y){ y < x ? x = y : 0; }
const int N = 500005,M = 50005,K = 70,INF = 2e8;
struct Data{
    int v1[N],v3[N],v20[N],v21[N],l1,l3,l12,l123,l20,l21;
    inline void init(){ l1 = l20 = l3 = 0; }
    inline void Ins(int w,int c){ if (w == 1) v1[++l1] = c; else if (w == 2) v20[++l20] = c; else v3[++l3] = c; }
    inline void work(){
        register int i;
        l12 = l1 + (l20<<1),l123 = l12 + l3 * 3,l21 = l20,memcpy(v21,v20,(l20+1)<<2);
        sort(v1+1,v1+l1+1),sort(v3+1,v3+l3+1);
        for (i = 1; i < l1; i += 2) v20[++l20] = v1[i]+v1[i+1]; sort(v20+1,v20+l20+1);
        v20[0] = 0; for (i = 1; i <= l20; ++i) v20[i] += v20[i-1]; v20[l20+1] = INF; 
        for (i = 2; i < l1; i += 2) v21[++l21] = v1[i]+v1[i+1]; sort(v21+1,v21+l21+1);
        v21[0] = l1 ? v1[1] : INF; for (i = 1; i <= l21; ++i) v21[i] += v21[i-1]; v21[l21+1] = INF;
    }
    inline int ask12(int x){
        if (x <= 0) return 0; if (x > l12) return INF;
        return (x&1) ? min(v21[x>>1],v20[x+1>>1]) : (v20[x>>1]);
    }
    inline int query(int x){
        if (x <= 0) return 0; if (x > l123) return INF;
        static int i,now,ans; now = 0,ans = ask12(x);
        for (i = 1; i <= l3; ++i) now += v3[i],x -= 3,upd(ans,now+ask12(x));
        return ans;
    }
}data;
int L; struct DPv{ int f[41]; inline void init(){ for (int i = 0; i <= L; ++i) f[i] = INF; } };
inline void upd(DPv &A,DPv &B){
    static int f[41]; register int i,j;
    for (i = 0; i <= L; ++i) f[i] = INF;
    for (i = 0; i <= L; ++i) for (j = 0; i+j <= L; ++j) upd(f[i+j],A.f[i]+B.f[j]);
    memcpy(A.f,f,(L+1)<<2);
}
vector<int> G,w[M],c[M],ans0[M],ans1[M]; vector<bool>is[M];
int m,n[M],s[M],len[M],sumw[M],ans;
int k,tp[K],ax[K],ay[K],bx[K],by[K],vc[K],cnt,px[13],py[13];
DPv dp1,now,f;
inline void solve(int S){
    register int i,j; int tt,sumc = 0;
    for (i = 1; i <= cnt; ++i)
        if (S>>(i-1)&1) sumc += c[px[i]][py[i]],sumw[px[i]] += w[px[i]][py[i]],is[px[i]][py[i]] = 1; else is[px[i]][py[i]] = 0;
    for (i = 1; i <= k; ++i) if (is[ax[i]][ay[i]] && is[bx[i]][by[i]]){
        if (vc[i] >= INF){ for (i = 1; i <= cnt; ++i) if (S>>(i-1)&1) sumw[px[i]] -= w[px[i]][py[i]]; return; }
        sumc += tp[i] == 1 ? -vc[i] : vc[i];
    }
    for (now = dp1,tt = 0; tt < G.size(); ++tt){
        for (i = G[tt],f.init(),j = 0; j <= L-sumw[i]; ++j) f.f[sumw[i]+j] = ans0[i][j];
        for (j = 0; j <= sumw[i]; ++j) f.f[sumw[i]-j] = ans1[i][j];
        upd(now,f);
    }
    upd(ans,now.f[L]+sumc);
    for (i = 1; i <= cnt; ++i) if (S>>(i-1)&1) sumw[px[i]] -= w[px[i]][py[i]];
}
int main(){
    register int i,j;
    read(m),read(L),ans = INF;
    for (i = 1; i <= m; ++i){
        read(n[i]),read(s[i]),L -= s[i],w[i].resize(n[i]),c[i].resize(n[i]),is[i].resize(n[i]);
        for (j = 0; j < n[i]; ++j) read(w[i][j]),read(c[i][j]);
    }
    L = max(L,0),read(k);
    for (i = 1; i <= k; ++i){
        read(tp[i]),read(ax[i]),read(ay[i]),read(bx[i]),read(by[i]); --ay[i],--by[i],vc[i] = INF; if (tp[i] <= 2) read(vc[i]);
        if (!is[ax[i]][ay[i]]){ ++cnt; is[ax[i]][ay[i]] = 1,px[cnt] = ax[i],py[cnt] = ay[i]; }
        if (!is[bx[i]][by[i]]){ ++cnt; is[bx[i]][by[i]] = 1,px[cnt] = bx[i],py[cnt] = by[i]; }
    }
    for (dp1.init(),dp1.f[0] = 0,i = 1; i <= m; ++i){
        data.init();
        for (j = 0; j < n[i]; ++j) if (!is[i][j]) data.Ins(w[i][j],c[i][j]); else len[i] += w[i][j];
        data.work();
        if (!len[i]){ for (j = 0; j <= L; ++j) f.f[j] = data.query(s[i]+j); upd(dp1,f); continue; }
        G.push_back(i); ans0[i].resize(L+1); for (j = 0; j <= L; ++j) ans0[i][j] = data.query(s[i]+j);
        ans1[i].resize(len[i]+1); for (ans1[i][0] = ans0[i][0],j = 1; j <= len[i]; ++j) ans1[i][j] = data.query(s[i]-j);
    }
    for (i = 0; i < 1<<cnt; ++i) solve(i);
    cout << (ans >= INF ? -1 : ans) << '\n';
    return 0;
}