• C. The Hard Work of Paparazzi
• D. Unshuffling a Deck

想着明天有事情就没打，摸鱼去了，但是后来忍不住看了下题目。

C. The Hard Work of Paparazzi

大意是有些明星会在特定位置特定时间出现一瞬间，如果这一瞬间你就在那个位置就能与他拍照。你每分钟可以上下左右移动一格。求最多能和多少明星拍照。

令 dp[i] 为处理到前 i 个明星并且和第 i 个明星拍照的答案。1000 分钟可以从任意位置走到任意位置，也就是说 dp[i] 最多只与 dp[i-999], ..., dp[i-1] 和 max(dp[1], ..., dp[i-1000]) 有关，强行 dp 即可。

注意走不到的 dp[i] 赋值为 -inf。

D. Unshuffling a Deck

大意是给一个排列，每次可以把整个排列分成若干区间，然后对区间的列表翻转（区间内不变，区间相对位置改变）。要求在 n 次操作内将区间排序。

u1s1，这题不难。假设已经将 1 到 k 这些数字排在一起并且单增或者单减，要让 k+1 也搞进来，分成 4 种情况：（以下只考虑 k=3）

1. X4XX123X，考虑分成 [X][4][XX123][X]，变成 XXX1234X。
2. X123XX4X，考虑分成 [X][1][2][3][XX4][X]，变成 XXX4321X。
3. X321XX4X，和 1 差不多。
4. X4XX321X，和 2 差不多。

这样只要 n-1 次操作就能全部单增或者单减了。如果单减就再操作一次搞单增即可。