难道说人的身高也需要用LONGINT来存储吗？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

题目看错了，郁闷

倒着做显然不需要考虑中间人,因为一定能保证有一个人比当前这两个低

边界啊 ,边界啊!!!!

正着做的边界啊!!!

从大到小读入

f表示前i个人分成j组的残疾程度

f=f+sqr(a[i]-a)

此题就是黑书习题中《佳佳的筷子》。方程和证明平方和都很简单，关键在于取中间最长的问题，先前我正向想了很久都很难满足这个条件，于是逆向思维，倒序求解，这样i从1到m, j每次从n-i*3+1就可以满足取得最长筷子的条件。

因为数组很大，建议开滚动数组

dPPPPPPPPPPPPPPPPPPPPPPPPPPP

汗下,开了5000*1000的数组竟然还能0MS出解..........

偶用了滚动数组优化的DP

复杂度是O(MN)

以下是DP方程,其中c[i]=(h[i]-h)*(h[i]-h)

d[j&1][i]=imin(d[j&1],d[(j&1)^1]+c);

从大到小排序 a[i]

f 表示前i个数中有j对跳舞组合时的最优解

应为要最优就必须是排序时相邻两数的在两边才最好

而中间的人最高，记 f=f+(a[i]-a)^2

如果不取a[j]就 记 f=f

所以 f=min{f=f+(a[i]-a)^2 | f=f}

黑书上《佳佳的筷子》

出题人就是强,我的程序第一遍全超,改了N久才A.

从后向前DP（我自己绝对想不到，瞟了眼题解才得到启发）

最先用了个O(n^3)的程序：

f表示将第i，i+1人组成一组作为这组左右两人，从第i人到最后构成j组的最小残疾值

f=min(f,(a[i]-a)^2+f[k,j-1])

i+2

这题果然很有趣.知道怎么动规却不一定调的出来.

为这题调了N久,要纪念下.

细节真的很重要!这题比起那些2重或3重循环再+个状态转移方程直接出解的有意义多了.

..我晕..怎么那么多方程没考虑中间的要比两边的高呢......汗

AC的第100题，纪念一下，但还是不知道为什么从后往前DP就一定能够保证有m个最高的

f为已经考虑第i个以后的数后,有j对数的最小残疾值

f=min(f,f+(a-a[i])^2)

边界为f=0

答案为f[1,m]

那怎么样保证一定有m个最高的人呢?????

因为１～２个数据没有ＡＣ的．．要注意．．读的时候应该反着读．．为什么要这样自己想．．

可以试试这个数据．．

1 3

1 4 4

反着输入正确结果是9..

正着输入是0..

知道动规方程的还不一定解的出来,建议大家不要看下面大牛的动规方程,因为我就是看了,才导致了自己没有了自己的思想,还是想自己想一下再做的好,毕竟一些细节处理,每个人有每个人的方法