CVBB ACM Team

给定n和m。问长度为n且总和为m的非负整数数列，相邻两项差的绝对值之和最大为多少。

贪心。n=1时答案为0，n=2时答案为m，n>2时答案为2m

水题，过

略

$n\times n$的方格，每个格子内有一个棋子。每次移动可以将一枚棋子移动到相邻的八个格子中的一个。每个格子中棋子最大数不限。现要将所有棋子移动到一个格内。问最少移动步数。

保证n是奇数

显然，最优策略是将所有棋子移到中间。然后随便推一推即可。

长度为n的数列一开始全是0。第i次操作，将最长的全为0的子段的中间改为i。求最终的数列。

用堆存下所有长度为0的子段。每次取出最长的，修改中间，并将两边再放进堆。

长度为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])$

$n\times m$的格子，每个格子给定一个高度。要从(1,1)走到(n,m)，只能往下或右走，且只能走到比当前高1的格子。花费1的代价可以让一个格子高度减1，问使得存在合法路径的最低花费

最优策略下，最终的合法路径上，一定有一个格子没有更改高度。

枚举每个格子，要求不更改其高度且强制走过这个格子。对每种情况，可以dp求出最小花费（或不存在这种可能）。