感谢各位大神

贴个方程吧

F[J]=MIN{F[J],F[J-1]+（W-W)^2&&(I>=j*3)}

感谢 ”litianren“

请问各位大牛们，这组数据怎么处理：

1 5

1 3 5 7 8

如果依照下面的方法 得到的结果是1 其匹配方式为7 8是最矮的，但这是不可能的

正确的解应该是4

求解

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

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

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

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

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

怎么 这么慢……

经典思想

终于AC......

天，连怎么对的都不知道

编译通过...

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

不知道为什么 用pascal打就AC 用C打就错 为什么~~~为什么~~~

#include

#include

#include

int main()

{

int a[5001],f[1001][5001],i,j,n,m;

scanf("%d %d\n",&m,&n);

for (i=n;i>=1;i--) scanf("%d",&a[i]);

for (i=1;i

我们可以撇开最高的人不管。

然后问题就变成了找到m个差的平方的和最小的数对。

显然这两个数需要是相邻的吧。

F前j个数取出i对

F=Min{F,F+(a[j]-a[j-1])^2}

当然，注意任何时候都要有j>=3*i。

（以上都假设数字是从大到小排列的）

20AC

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

program Ltr;

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

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

rag,tp1,tp2,i,j,m,n,tmp,mn:longint;

begin

readln(m,n);

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

for i:=1 to m do begin

rag:=3*i;

for j:=rag to n do begin

tp1:=b;

tp2:=b+sqr(a[j-1]-a[j]);

if (tp1=rag+1) then b:=tp1

else b:=tp2;

end;

end;

writeln(b[m,n]);

end.

记录号 Flag 得分 记录信息 环境 评测机 程序提交时间

R1011184 Accepted 100 From 究级武神霸斩－

　 P1061 FPC Vijos Dolphin 2008-11-6 17:23:10

From Tsuzuki

迎春舞会之三人组舞 迎春舞会 系列

编译通过...

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

晕死，数组开大了

for i:=1 to m do

for j:=2*i to n do begin

f:=f;

if ((m-i)*3f+sqr(h[j])) then

f:=f+sqr(h[j]);

end;

编译通过...

├ 测试数据 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：答案正确... 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：答案正确... 9ms

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

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

var a:array[1..5000]of integer;

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

i,j,m,n:integer;

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

begin

if a>b then exit(b) else exit(a);

end;

begin

readln(m,n);

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

for i:=1 to n do for j:=1 to m do s:=99999999;

for i:=n-2 downto 1 do

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

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

writeln(s[1,m]);

end.

这一句

"for i:=1 to n do for j:=1 to m do s:=99999999;"

我原来是用fillchar,然后再回头把s都赋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：答案正确... 0ms

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

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

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

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

JHOI...

耗时太长了 我的记录就不好意思印出来了

不过题目还不是太难的 只要多考虑一下中间的那个高个子就行了

加个限制条件:如果要凑出一对,就必须保证后面要有一个未配对的高个子

Orz JHOI

补楼上。。动归时需要保证剩下的人数大于剩下的组数乘以3.。

记忆化搜索

用f[i][j]表示前i个人中选出j组.

特别注意如果定义为后i个,那么i之前的状态就会影响i的状态,造成后效性.

定义为前i个人,就可以保证i只后的人都可以与这两个人组成一组.

分两种情况:

1.第i和i-1个人构成一组,f[j-1]+compute(i,i-1),i>=2,j>=1.

2.第i和i-1个人不构成一组,即其平行状态f[j].

边界:

f[k][0]=0

(1

编译通过...

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