P3212 [HNOI2011] 任务调度

题意nnn个任务第iii个任务需要在AAA机器上执行aia_iai​时间在BBB机器上执行bib_ibi​时间每个任务有一个类型tit_iti​。类型111需要先在AAA机器上执行再在BBB机器上执行。类型222需要现在BBB机器上执行再在AAA机器上执行。类型333无要求。问把所有任务完成的最短时间。n≤20n\le20n≤20。思路先暴力枚举出所有ti3t_i3ti​3的物品先在AAA执行还是现在BBB执行。现在问题变成了nnn个任务每个任务要先在A/BA/BA/B上执行问把全部任务执行完成的总时间。显然最优情况是max⁡(∑ai,∑bi)\max(\sum a_i,\sum b_i)max(∑ai​,∑bi​)但是有时候取不到。设初始在AAA的物品集合为SAS_ASA​初始在BBB的物品集合为SBS_BSB​不妨设∑i∈SAai≥∑i∈SBbi\sum_{i\in S_A}a_i\ge\sum_{i\in S_B}b_i∑i∈SA​​ai​≥∑i∈SB​​bi​那么AAA机器工作的时间一定是满的即从000工作到∑ai\sum a_i∑ai​考虑BBB机器。设fsf_sfs​表示AAA机器完成了sss中的物品(s⊂SA)(s\subset S_A)(s⊂SA​)BBB机器最少有多久没工作。显然当∑i∈sai≤∑i∈SBbi\sum_{i\in s}a_i\le\sum_{i\in S_B}b_i∑i∈s​ai​≤∑i∈SB​​bi​时fsf_sfs​为000否则枚举上一个完成的物品进行转移。时间复杂度未知估算一下大概是2×1082\times10^82×108但是跑不满。代码// Problem: P3212 [HNOI2011] 任务调度// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P3212// Memory Limit: 128 MB// Time Limit: 1000 ms//// Powered by CP Editor (https://cpeditor.org)#includebits/stdc.husingnamespacestd;namespaceIO{templatetypenameTinlinevoidread(Tx){x0;charcgetchar();boolf0;while(!isdigit(c))c-?f1:0,cgetchar();while(isdigit(c))xx*10c-0,cgetchar();f?x-x:0;}templatetypenameTinlinevoidwrite(T x){if(x0){putchar(0);return;}x0?x-x,putchar(-):0;shortst[50],top0;while(x)st[top]x%10,x/10;while(top)putchar(st[top--]0);}inlinevoidread(charc){cgetchar();while(isspace(c))cgetchar();}inlinevoidwrite(charc){putchar(c);}inlinevoidread(strings){s.clear();charc;read(c);while(!isspace(c)~c)sc,cgetchar();}inlinevoidwrite(string s){for(inti0,lens.size();ilen;i)putchar(s[i]);}templatetypenameTinlinevoidwrite(T*x){while(*x)putchar(*(x));}templatetypenameT,typename...T2inlinevoidread(Tx,T2...y){read(x),read(y...);}templatetypenameT,typename...T2inlinevoidwrite(constT x,constT2...y){write(x),putchar( ),write(y...),sizeof...(y)1?putchar(\n):0;}}usingnamespaceIO;constintmaxn30,inf1000000000;intn,A[maxn],B[maxn],t[maxn],cnt3,cnt_a,cnt_b,f[1048576],sum2a[1048576],sum2b[1048576];shorthv[1048576][21],cnt_hv[1048576];structnode{inta,b;}a[maxn],b[maxn];intcalc(){intsuma0,sumb0;for(inti1;icnt_a;i)sumaa[i].a;for(inti1;icnt_b;i)sumbb[i].b;if(sumasumb){swap(a,b);swap(cnt_a,cnt_b);swap(suma,sumb);for(inti1;icnt_a;i)swap(a[i].a,a[i].b);for(inti1;icnt_b;i)swap(b[i].a,b[i].b);}for(ints0;s(1cnt_a);s){sum2a[s]sum2b[s]0;for(inti1;icnt_hv[s];i)sum2a[s]a[hv[s][i]].a;for(inti1;icnt_hv[s];i)sum2b[s]a[hv[s][i]].b;}for(ints0;s(1cnt_a);s){intsumsum2a[s];if(sumsumb){f[s]0;continue;}f[s]inf;for(intii1;iicnt_hv[s];ii){intihv[s][ii];intlt(s^(1i-1));inttbsumbsum2b[lt]f[lt];inttasum;f[s]min(f[s],f[lt]max(0,ta-tb));}}intsumalla0,sumallb0;for(inti1;icnt_a;i)sumallaa[i].a,sumallba[i].b;for(inti1;icnt_b;i)sumallab[i].a,sumallbb[i].b;returnmax(sumalla,f[(1cnt_a)-1]sumallb);}signedmain(){for(inti0;i1048576;i)for(intj1;j20;j)if(i(1j-1))hv[i][cnt_hv[i]]j;read(n);for(inti1;in;i)read(t[i],A[i],B[i]),cnt3(t[i]3);intansinf;for(inti0;i(1cnt3);i){intnwcnt0;cnt_acnt_b0;for(intj1;jn;j){if(t[j]1)a[cnt_a]{A[j],B[j]};elseif(t[j]2)b[cnt_b]{A[j],B[j]};else{if(i(1nwcnt))a[cnt_a]{A[j],B[j]};elseb[cnt_b]{A[j],B[j]};nwcnt;}}ansmin(ans,calc());}write(ans);return0;}