うーんもったいない。
https://community.topcoder.com/stat?c=problem_statement&pm=15829
問題
N個の仕事を行いたい。
各仕事は2か月連続で行う必要があり、1か月目はA[i]人、2か月目はB[i]の人を必要とする。
複数の仕事を同時に行うことはできるが、先の仕事を追い越すことはできない。
W人の人で全仕事を行うのに最低何か月かかるか。
解法
まず、AやBの累積和を取っておく。
以下をそれぞれ考える。
f(R) := R番目までの仕事を完了する最短時間。
g(L,R) := 最終月に[L,R]の区間の仕事を行う場合に、R番目までの仕事を完了する最短区間。
fは単調増加で、gもLを決めるとRに対し単調増加である。
g(L,R)の次の遷移を考える。
- 最終月に[L,R]以外の仕事を行わない場合を考えるとf(R) = min(g(L,R))
- 最終月に、新たに[(R+1),X]の区間の1か月目の仕事をかぶせる場合、g(R+1,X)=min(g(L,R)+1, f(R)+2)
- なお、この時[(R+1),X]の1か月目の仕事と[L,R]の2か月目の仕事がW人以下で賄え、[(R+1),X]の2か月目の仕事もW人で賄えることを確認しなければならない。
[L,R]に対しXを総当たりするとO(N^3)かかりTLEするが、尺取り法の要領でXを求めるとO(N^2)で収まる。
int L0,L1,L; int A[5050]; int B[5050]; ll SA[5050]; ll SB[5050]; int dp[5050][5050]; class TwoMonthScheduling { public: int minimumMonths(int workers, vector <int> firstMonth0, vector <int> firstMonth1, vector <int> secondMonth0, vector <int> secondMonth1) { L0 = firstMonth0.size(); L1 = firstMonth1.size(); int i0,i1,i; FOR(i1,L1) FOR(i0,L0) { A[i1*L0+i0+1]=min(workers, firstMonth0[i0]^firstMonth1[i1]); B[i1*L0+i0+1]=min(workers, secondMonth0[i0]^secondMonth1[i1]); SA[i1*L0+i0+1]=SA[i1*L0+i0]+A[i1*L0+i0+1]; SB[i1*L0+i0+1]=SB[i1*L0+i0]+B[i1*L0+i0+1]; } int N=L0*L1; int x,y,W=workers; FOR(x,N+2) FOR(y,N+2) dp[x][y]=101010; int mi=101010; dp[1][0]=0; int L,R,R2; for(L=1;L<=N;L++) { int R2=0; for(R=N;R>=L;R--) dp[L][R]=min(dp[L][R],dp[L][R+1]); for(R=L;R<=N;R++) if(SA[R]-SA[L-1]<=W && SB[R]-SB[L-1]<=W) { //completely new dp[L][R]=min(dp[L][R],dp[L][0]+2); //fin dp[R+1][0]=min(dp[R+1][0],dp[L][R]); for(R2=max(R+1,R2);R2<=N;R2++) { if(SB[R]-SB[L-1]+SA[R2]-SA[R]>W || SB[R2]-SB[R]>W) break; } while(R2>R && (SB[R]-SB[L-1]+SA[R2]-SA[R]>W || SB[R2]-SB[R]>W)) R2--; dp[R+1][R2]=min(dp[R+1][R2],dp[L][R]+1); } mi=min(mi,dp[L][N]); } mi=min(mi,dp[N+1][0]); return mi; } }
まとめ
O(N^3)をいかにO(N^2)にするかという問題。