今天两道一次AC了，都是打完过了样例提交直接通过，我感到莫名的感动……

初始化的时候好像分为一组只要找a[(i+j) div 2]就行了……中位数

那么就是典型的分组dp了！

f:=min(f[k,j-1]+g[k+1,i]);

程序25行，好像稍微长了一点……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一次 哈哈哈哈

纪念下,半星

纯属数学题……

连飓风音速都能做还叫NOI？

0ms秒杀。

数组开大一点，用int64。但要小心内存溢出。

短，永远不属于我的程序，哎，是好还是坏呢

program P1242;

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

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

f:array[0..300,0..30] of longint;

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

begin

if ab then exit(b)

else exit(a);

end;

function change(s,t:longint):longint;

var tot,mid,i,j:longint;

begin

tot:=0;

mid:=a[(t+s) div 2];

for i:=s to t do

tot:=tot+abs(mid-a[i]);

change:=tot;

end;

Begin

fillchar(f,sizeof(f),$f0);

readln(n,m);

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

for i:=1 to n do f:=change(1,i);

for i:=1 to n do

for j:=2 to m do

if i>=j then

for k:=0 to i-1 do

f:=min(f,f[k,j-1]+change(k+1,i))

else break;

writeln(f[n,m]);

end.

膜拜楼下的牛们，看了你们的题解，小菜终于会了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

...比较傻。。本来想说遇到特殊情况就输出的，免得麻烦还错了。。。但是输出后忘了exit，把答案输出了两遍。。。。哭

program p1242;

var

a,b:array[0..400,0..400]of longint;

c:array[0..400]of longint;

n,m,i,k,j:longint;

begin

readln(n,m);

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

for i:=1 to n do

for j:=i to n do

for k:=i to j do a:=a+abs(c[k]-c[(i+j)div 2]);

fillchar(b,sizeof(b),1);

for i:=1 to n do b:=a[1,i];

for i:=2 to m do

for j:=1 to n do

for k:=1 to j do

if b[k,i-1]+a[k+1,j]

编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms-------------------------Accepted 有效得分：100 有效耗时：0ms难看。。。

var

n,m,j,i,k,q:longint;

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

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

//f=min(f[k,j-1]+long(k+1,i),f[k,j]);

begin

readln(n,m);

for i:=1 to n do

read(a[i]);

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

fillchar(w,sizeof(w),0);

for i:=1 to n do

for j:=1 to n do

begin

k:=a[(j+i) div 2];

for q:=i to j do

w:=w+abs(a[q]-k);

end;

for i:=1 to n do

f:=w[1,i];

for j:=2 to m do

for i:=j to n-m+j do begin

f:=maxlongint;

for k:=j-1 to i-1 do

if f>f[k,j-1]+w[k+1,i] then

f:=f[k,j-1]+w[k+1,i];

end;

writeln(f[n,m]);

end.

我的题解 - My Solution

题解 Solution

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

跟马棚问题还有乘法问题，几乎一样，就是最短距要搞一下

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

f,p:array [0..400,0..400] of longint;

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

begin

{ assign(input,'post.in');

assign(output,'post.out');

reset(input);

rewrite(output); }

readln(n,m);

for i:=1 to n do

read(a[i]);

for i:=1 to n do

for j:=i to n do begin

k:=(i+j) div 2;

for o:=i to j do

p:=p+abs(a[o]-a[k]);

end;

for i:=1 to n do

f:=p[1,i];

for j:=2 to m do

for i:=j to n-m+j do begin

f:=maxlongint;

for k:=j-1 to i-1 do

if f[k,j-1]+p[k+1,i]

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

二十行程序的问题

没看题解1次AC了。

先将村庄排序，用f表示前i个村庄修j个XX时最小值，然后枚举

从k到i修建一个，地点为中位数，然后DP即可

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

IOI也不难吗！被我一下AC

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

本题也是一道动态规划问题，详细分析请看文本附件（邮局解题报告）。将n个村庄按坐标递增依次编号为1，2，……，n，各个邮局的坐标为d[1..n]，状态表示描述为：m表示在前j个村庄建立i个邮局的最小距离和。所以，m[p,n]即为问题的解，且状态转移方程和边界条件为：

m[1,j]=w[1,j] i≤j

其中w表示在d之间建立一个邮局的最小距离和，可以证明，当仅建立一个邮局时，最优解出现在中位数，即设建立邮局的村庄为k，则 ，于是，我们有：

同时，令s=k，记录使用前i-1个邮局的村庄数，便于在算出最小距离和之后构造最优建立方案。

上述算法中w可通过O(n)时间的预处理，在O(1)的时间内算出，所以，该算法的状态总数为O(n*p)，每个状态转移的状态数为O(n)，每次状态转移的时间为O(1)，该算法总的时间复杂度为O(p*n2)。

[算法优化]

本题的状态转移方程与①式十分相似，因此我们猜想其决策是否也满足单调性，即

s≤s≤s

首先，我们来证明函数w满足四边形不等式，即：

设 ， ，下面分为两种情形，z≤y或z>y，下面仅讨论z≤y，z>y的情况是类似的。

由i≤z≤y≤j有：

接着，我们用数学归纳法证明函数m也满足四边形不等式。对四边形不等式中“长度”l=j’-i进行归纳：

当i=i’或j=j’时，不等式显然成立。由此可知，当l≤1时，函数m满足四边形不等式。

下面分两种情形进行归纳证明

情形1：ij的情况是类似的。

情形2：i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我DP道路上具有里程碑意义的一题。

Accepted 有效得分：100 有效耗时：1100ms ???

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一次ac!!!

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

= = 居然做了这么长时间才AC，方程很快就写出来了，但就是不能AC

此题动规可以在范围上优化，但由于此题数据巨弱。。没优化也可以秒杀。。- -

这里说下优化范围需要注意的地方

1.动规，预处理的数组要用Long(废话)

2.动规的数组初始化不能是Maxlongint(除非你数组定义成int64的),否则会越界，

Maxlongint div 2 也行

3.边界f[0,i]=0 f=0 (0

看了各位大牛的题解,头脑清醒多了，多谢各位大牛了!!!