abs.....忘了写....

真的是贪心啊

DP肯定要TLE

额，郁闷，代码打错，爆了0，T T

这个题目贪心证明我是这么想的

设改变后数列一段为a,a,a-k,a-k,a+m,a+m，这样改成a,a,a,a,a+m,a+m代价一样

如果中间a-k段长度大于2，那么后者代价比前者大

所以前者一定是一个最优序列

又贪心方法一定只能造成如前所述序列，所以全数列最优

如果某个 a_i 比两边都高或都低，就修改它，使之和某一边一样高

Vijos C++ 用的是 MinGW G++ 吧

long long 格式化字符串为 %I64d，%lld 似乎就当作 %ld 处理

看我最短的C++程序

#include

#include

long long a[100000+10],ans=0;

int i,n;

int main(){

std::cin>>n;

for(i=1;i>a[i];

for(i=2;ia && a[i]>a)ans+=a[i],ans-=a[i]=a>?a;

if(a[i]

“其实这题很简单”——From 姜碧野大牛

以下非FROM姜碧野大牛：

首先两头的不管，因为你怎样移动都不会小于最优值。

所以冲中间作

因为一个数如果大于旁边俩数的最大值，或小于最小值，这样耗费的体力会比最优值大

但因为符合最优值的数是在一个区间中，所以为了移动所耗的体力最小

所以就要把数赋成区间的边界值。但如果数本身就在区间里头就不用管。

为什么会保证全数列最优呢？

答：假设A改变了，那A肯定是不用改变或者变成与A相等的

这个定论不难证明，想一想就会明白。所以A会保证在A~A

这个区间里头。

因此，这种贪心方法可以贪出一种最优方法，进而能得出最优解。。。

//路人甲：boyzkk大牛真神奇，人品爆发了，一撞撞对。。。⊙﹏⊙b汗

C/C++用printf输出的要用%I64d而不是%lld，不然40分..

考试的时候倒着做。。结果最后一题还是拿了个0分。。第一题没交。。

3ci

杯具...

终于A了！！！

哭啊!考试时没做这题!!想到了方法,没去做!!!!

浪费Rp啊，居然把min和max写反了。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

我最不擅长贪心……

悲剧啊，longint不行，只过3个点，要改int64

比赛时胡乱的想了一个3个相邻的数的方法, 匆匆交上...没想到AC...

max打成了min....

第80个提交！

第39个AC！

庆祝一下！

方法见lx！

原来AC的方法就是这样做的。

害得我比赛时，想到了却不敢这么做。

RP不足，信心也不足啦！

现在一次就AC了。(=@__@=)

不难证明，相邻3个数，若中间的高于两边的（例如：a，a+5，a），它们做差的绝对值相加就是10.而先把它削矮至a，本来要加两次的5，只要一次性加入结果，而再次做差的绝对值相加就为0.（两边不相等，就取差的绝对值小的那个）若中间的低于两边的也是同理。若中间的介于两边之间，不难发现结果就是两边数的差的绝对值，若改变高度，这个值不变，还要再多加改变量的部分（白费功夫~(≧▽≦)/~啦啦啦）。

只是为什么能保证在整一列数上来说，也是最优的，我就还没想通……