bnu-faraway/2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018)
Info
Date:2018.10.23
Solutions
A Altruistic Amphibians
unsolved
B Baby Bites
solved by
’s solution
C Code Cleanups
solved by
’s solution
D Delivery Delays
upsolved by ghc
ghc’s solution
二分套dp。\(dp[i]\)表示从店里出发,送完前\(i\)份外卖且回到店里的最早时间,有
\(dp[i]=min_{k<i} \{ max(dp[k],t[i])+f(k+1,i) \}\)
其中\(f(x,y)\)表示从店里出发,按顺序送完第\(x\)至第\(y\)份外卖后回到店里的最短时间,
\(f(x,y)=dis[1][x]+dis[x][x+1]+dis[x+1][x+2]+...+dis[y-1][y]+dis[y][1]\)
二分答案后,认为每份外卖订单的等待时间不能超过\(mid\)。dp转移时会对k产生限制,即\(max(dp[k],t[i])+dis[1][k+1]+dis[k+1][k+2]+...+dis[j-1][j] < s[j]+mid , k+1 \leq j \leq i\)
从后往前枚举k,即可实现对上述限制的\(O(1)\)更新,dp复杂度\(O(n^2)\)
E Explosion Exploit
solved by gjy
gjy’s solution
F Firing the Phaser
unsolved
G Game Scheduling
unsolved
H House Lawn
solved by gjy
gjy’s solution
I Intergalactic Bidding
solved by
’s solution
J Jumbled String
solved by
’s solution
K King’s Colors
solved by
’s solution