whyvine的解题报告：

http://blog.sina.com.cn/s/blog_618b6ea70100eglj.html

里面分析了为什么f是正确的而f是错误的

编译通过...

├ 测试数据 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

倒着dp真的不用考虑中间最高的那个

var

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

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

n,m:longint;

procedure init;

var

i:longint;

begin

readln(m,n);

for i:=1 to n do read(a[n-i+1]);

end;

procedure dp;

var

i,j:longint;

begin

for i:=1 to m do

for j:=1 to n do

if j>=i*3 then

begin

f[i][j]:=f[j-2]+sqr(a[j-1]-a[j]);

if j-1>=i*3 then

if f[i][j]>f[i][j-1] then f[i][j]:=f[i][j-1];

end;

writeln(f[m][n]);

end;

begin

init;

dp;

end.

但是，还是看了题解才会做。。。

PROGRAM wudaoIv1061Idougui;

var m,i,t,j,n:longint;

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

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

begin

readln(m,n);

for i:=n downto 1 do

read(a[i]);

for i:=1 to m do begin

t:=3*i;

for j:=t to n do

if (j>t) and (f

此好题哉

花了一个半小时才想明白。

我明白了一个很大的道理，就是我一直都在想的转移方程没有考虑到所有状态。

这就是为什么要倒着做的原因，虽然我只懂得了这一方法。

因为正着不能既保证能够得到中间较高的人，又得到比较小的差值

而倒着做首先保证了能得到中间较高的人，然后只需要考虑i-1和i-2的状态，这样就可以得到最小差值。

虽然 程序才写了17行，都不用滚动

可以在空间上优化优化，var f:array[0..2,0..1000] of longint;就行勒

这个题难度3，但似乎是我写得最短的程序，只有18行，而且一次AC~

额，小于等于打成小于还有70分……汗

人生第一次在vijos上AC一道难度3的题……虽然第一次输多了点东西。。。。

就是考虑连带关系，和他的有序能干什么~~

skanony

其实某些时候，我们可以......

short int f[5001][1001];

DP,一定要倒着来，用-1去标记不存在的，想出来比较简单~

Program P1061;

var f:array[0..5100,0..1100] of longint;

a:array[0..5100] of longint;

i,j,n,m:longint;

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

begin

if a=-1 then exit(b);

if b=-1 then exit(a);

if a>b then exit(b)

else exit(a);

end;

Begin

fillchar(f,sizeof(f),0);

readln(m,n);

for i:=1 to n do read(a[i]);

for i:=n downto 1 do

for j:=1 to m do

if n-i+1>=j*3 then

f:=min(f,f+sqr(a-a[i]))

else begin f:=-1;break;end;

writeln(f[1,m]);

end.

C语言的朋友……数组是不可能开到[5001][1001]的了，用动态数组吧。

头文件Include一个malloc.h

long *f;/*注意是两个*号*/

f=(long*)malloc(sizeof(long*)*(n+1));

f[0]=(long*)malloc(sizeof(long)*(m+1)*(n+1));

for(a=1;a

简单DP

不愧是src250,题解都写得那么XE

感谢guoti12321大牛的思路提供与KAI大牛得debug

还有我自己的编码以及加工

感谢人民感谢党……………………………………

那个……就用guori12321的做法就好，只是记住数据要倒着读进来

具体为什么吗……

对着那个try（i,i）好好想想，正着读的话，i不就是最高的了吗

总算AC了，花了我一下午和一晚上 不过对这种DP总算有了点感觉

DP要注意范围，下标的运用，最重要的是方程以及边界 这道题理解后会发现也不是很难

fillchar(f,sizeof(f),0);

f[2,1]:=try(1,2);

for i:=3 to n do

for j:=1 to min(i div 3, m) do

begin

if 3*j=i then f:=f+try(i-1,i)

else

f:=min(f,f+try(i-1,i));

end;

那个 if 3*j=i then 很重要，否则边界就不对了，会全部输出0的

另外，庆祝下我会发彩色的字了！！！

Flag　 　Accepted

题号 　 P1061

类型(?)　　动态规划

通过 　　1300人

提交 　3584次

通过率 36%

难度 3

呵呵，第1300个通过的

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

n,m,k,l,i,j,o,p,s:longint;

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

begin

readln(m,n);

for i:=n downto 1 do

read(a[i]);

fillchar(f,sizeof(f),$7F);

for i:=1 to n do

f:=0;

for j:=1 to m do begin

f:=maxlongint div 2;

for i:=3*j to n do begin

if f

编译通过...

├ 测试数据 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

好假的测评.........第一次UNAC........没有原因和记录....

第二次AC= =很诡异...........不信可以看看我的记录.......RUNNING

编译通过...

├ 测试数据 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：运行时错误...| 错误号: 103 | 文件未打开

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

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

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

├ 测试数据 18：运行时错误...| 错误号: 103 | 文件未打开

├ 测试数据 19：运行时错误...| 错误号: 103 | 文件未打开

├ 测试数据 20：运行时错误...| 错误号: 103 | 文件未打开

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

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

灵异事件！太WS了！

编译通过...

├ 测试数据 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

完全一样的程序，结果就是这么不一样！

我用的是很朴素的DP算法。将高度倒着读进来。本来想DP记录前i个人分j组的最小残疾程度，但是转移超时。于是采用了滚动DP。只记录与当前第i个人相邻的前3个人的情况。这样DP[4,j]=min(DP[1,j-1],DP[2,j-1])+sqr(h[i]-h）就行了。不用DP[3,j]的值是因为必然用相邻的两个人作为同组的矮人比间隔的更好。这样时间复杂度为C*M*N的，秒了。

每一层循环

先要判断i是否大于等于2*j

如若满足则

有以下动态方程：

f:=f;

f:=min(f,f+sqr(da[i]-da));

(因为应当满足最后有足够的高个人数，因此上述方程应满足 (m-j)*3

原来有时不能直接套方程