注意到当a

终于ac了，感觉真好啊！

那个大牛帮我解释一下为什么要倒序？谢谢！

倒推解决最高+相邻最优。。。

自己做肯定想不到。。

看来一定要拓宽思路。。。

边界问题是怎么想到j是从3*i到n的，真想不到

刚开始以为要按顺序没思路。。

已经令我呕吐的题目。。。

program zju1234;

var a:array[0..5000] of longint;

f:array[0..5000,0..5000] of longint;

n,k,i,j:longint;

function min(a,b:longint):longint;

begin

if a

编译通过... ├ 测试数据 01：答案正确... 0ms ├ 测试数据 02：答案正确... 0ms ├ 测试数据 03：答案正确... 0ms ├ 测试数据 04：运行时错误...|错误号: 216 ├ 测试数据 05：运行时错误...|错误号: 216 ├ 测试数据 06：运行时错误...|错误号: 216 ├ 测试数据 07：运行时错误...|错误号: 216 ├ 测试数据 08：运行时错误...|错误号: 216 ├ 测试数据 09：运行时错误...|错误号: 216 ├ 测试数据 10：运行时错误...|错误号: 216 ├ 测试数据 11：运行时错误...|错误号: 216 ├ 测试数据 12：运行时错误...|错误号: 216 ├ 测试数据 13：运行时错误...|错误号: 216 ├ 测试数据 14：运行时错误...|错误号: 216 ├ 测试数据 15：运行时错误...|错误号: 216 ├ 测试数据 16：运行时错误...|错误号: 216 ├ 测试数据 17：运行时错误...|错误号: 216 ├ 测试数据 18：运行时错误...|错误号: 216 ├ 测试数据 19：运行时错误...|错误号: 216 ├ 测试数据 20：运行时错误...|错误号: 216 ------------------------- Unaccepted 有效得分：15 有效耗时：0ms

无语…… 然后f数组开[0..10000,-1..5000]，结果……

编译通过... …………（此处省略）Accepted 有效得分：100 有效耗时：0ms

强烈怀疑该题范围有误！！！支持litianren大牛的说法，赞ing。别忘了倒着输入。状态方程 f:=min{f,f+sqr(a[j-1]-a[j])}; i为组数，j为人数。剩下的要看楼下litianren大牛的程序，绝对有效。我还赋了初值 f=0 f[0,i]=0 也许是画蛇添足吧。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 25ms

├ 测试数据 19：答案正确... 72ms

├ 测试数据 20：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：169ms

吐血，C++数组开到5000*1000只得90分，后来急了开10000*2000过了

正确率啊

弄了一个超短的.30 line

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 25ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 41ms

├ 测试数据 19：答案正确... 72ms

├ 测试数据 20：答案正确... 72ms

这就是Dragon的恐怖实力：居然没有秒杀

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

动态方程好写，但是程序不好写.....唉，要倒着，真是神了！！！

f:=min(f,f+sqr(a[j-1]-a[j]));

具体代码，参看下面李忠泽同学的

program p1061;

var

a:array[1..6000] of integer;

f:array[0..1,0..1000] of longint;

mm:longint; n,m,i,j:integer;

function min(x,y:longint):longint;

begin

if xi then mm:=10000000

else

mm:=min(f[0,j],f[1,j-1]+sqr(a[i]-a));

f[1,j]:=f[0,j]; f[0,j]:=mm;

end;

writeln(f[0,m]);

end.

用了滚动数组，这一题的DP方程貌似要进行最优证明

f:=min{f,f+sqr(h[i]-h)}; 为什么只会出现第i个人（1）不和第i-1个人搭配(2)和第i-1个人搭配？？？ 因为如果第i个人和前i-2个人中的任一个搭配，则不会比和第i-1个人搭配优，若第i个人和他后面的人搭配，这种情况会被他后面的人的动规方程考虑到，所以只有两种情况!!!!!!!!!!!!!!!!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 9ms

├ 测试数据 19：答案正确... 41ms

├ 测试数据 20：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：91ms

汗呐 没秒杀

program a9_5;

var dp:array[0..1,0..5001]of longint;

ind:array[0..5001]of longint;

ans,i,j,k,n,m,now,last:longint;

function min(a,b:longint):longint;

begin if a>b then min:=b else min:=a;end;

begin

readln(m,n);

for i:=1 to n do

read(ind[i]);

for i:=1 to m do

begin

now:=i and 1;

last:=1- now;

dp[now,i*2-1]:=maxlongint;

for j:=i*2 to n-((m-i)*3+1) do

dp[now,j]:=min(dp[last,j-2]+sqr(ind[j]-ind[j-1]),dp[now,j-1]);

for j:=n-((m-i)*3) to n do

dp[now,j]:=dp[now,j-1];

end;

ans:=maxlongint;

for i:=m*2 to n-1 do

if dp[m and 1,i]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案错误...程序输出比正确答案长

├ 测试数据 02：答案错误...程序输出比正确答案长

├ 测试数据 03：答案错误...程序输出比正确答案长

├ 测试数据 04：答案错误...程序输出比正确答案长

├ 测试数据 05：答案错误...程序输出比正确答案长

├ 测试数据 06：答案错误...程序输出比正确答案长

├ 测试数据 07：答案错误...程序输出比正确答案长

├ 测试数据 08：答案错误...程序输出比正确答案长

├ 测试数据 09：答案错误...程序输出比正确答案长

├ 测试数据 10：答案错误...程序输出比正确答案长

├ 测试数据 11：答案错误...程序输出比正确答案长

├ 测试数据 12：答案错误...程序输出比正确答案长

├ 测试数据 13：答案错误...程序输出比正确答案长

├ 测试数据 14：答案错误...程序输出比正确答案长

├ 测试数据 15：答案错误...程序输出比正确答案长

├ 测试数据 16：答案错误...程序输出比正确答案长

├ 测试数据 17：答案错误...程序输出比正确答案长

├ 测试数据 18：答案错误...程序输出比正确答案长

├ 测试数据 19：答案错误...程序输出比正确答案长

├ 测试数据 20：答案错误...程序输出比正确答案长

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：0 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

f......

是 2 不是 3

题解 http://254117343.blog.163.com/

分筷子改进版....

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

懂了。。。thank 楼上牛们