Warning: session_start(): open(/tmp/sess_645640e27264ddc63948070e3309854d, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/8/878e000dca5c08fe55e62fff31fad8b7.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====A - Most Unstable Array====
===题意===
给定n和m。问长度为n且总和为m的非负整数数列，相邻两项差的绝对值之和最大为多少。
===思路===
贪心。n=1时答案为0，n=2时答案为m，n>2时答案为2m
====B - Two Arrays And Swaps====
===题意===
水题，过
===思路===
略
====C - Board Moves====
===题意===
$n\times n$的方格，每个格子内有一个棋子。每次移动可以将一枚棋子移动到相邻的八个格子中的一个。每个格子中棋子最大数不限。现要将所有棋子移动到一个格内。问最少移动步数。
保证n是奇数
===思路===
显然，最优策略是将所有棋子移到中间。然后随便推一推即可。
====D - Constructing the Array====
===题意===
长度为n的数列一开始全是0。第i次操作，将最长的全为0的子段的中间改为i。求最终的数列。
===思路===
用堆存下所有长度为0的子段。每次取出最长的，修改中间，并将两边再放进堆。
====E - K-periodic Garland====
===题意===
长度为n的灯，给定开关状态。再给定k。现要求开/关某些灯，使得最终任意两个相邻的开着的灯距离都为k。求最少开关次数。
===思路===
s1，s2分别记录原先开着的灯的前缀、后缀和。dp[i]表示，只考虑前i盏灯，且必须开第i盏灯的最小开关次数。
若i原先开着，$dp[i]=\min(dp[i-k]+s1[i-1]-s1[i-k],s1[i-1])$，否则$dp[i]=\min(dp[i-k]+s1[i-1]-s1[i-k],s1[i-1])+1$。
最终答案为$\min(dp[i]+s2[i+1],s1[n])$
====F - Decreasing Heights====
===题意===
$n\times m$的格子，每个格子给定一个高度。要从(1,1)走到(n,m)，只能往下或右走，且只能走到比当前高1的格子。花费1的代价可以让一个格子高度减1，问使得存在合法路径的最低花费
===思路===
最优策略下，最终的合法路径上，一定有一个格子没有更改高度。
枚举每个格子，要求不更改其高度且强制走过这个格子。对每种情况，可以dp求出最小花费（或不存在这种可能）。