CF Edu109

A

gcd水过

B

分类讨论，很像昆明那道题，看上去是个很复杂的题目，实际上是可以找结论的。主要是不要想歪了。B题就是一个结论题目。答案只有0,1,2,3四种。
0就是每一个数都在自己位置.
1就是左右两端的数字(1或者n)有一个不在自己的位置上。
2和3就是1和n都不在自己的位置上并且如果1和n对调就是3。

C

暂时没写

D

开始一直以为是贪心 ,但是WA。
现在想想，贪心的思路应该是不对的。(主要是贪心的千奇百怪，贪了两个都WA在第八个点)
之后看了fxx学长的思路，写出来了(但是感觉DP如果别人已经把方程设计出来了，就没什么意思了)。
\(dp[\)前i个人\(][\)放到前j个空位\(]\)最少需要的花费。如果有x个人，y个空位，那么答案就是\(dp[x][y]\)
转移方程:
(1)如果第i个人不在第j个位置:
\(dp[i][j] = dp[i][j-1]\)
(2)如果第i个人在第j个位置:
\(dp[i][j] = dp[i-1][j-1]+花费\)