测评机: Xeost[5]
得分: 100分 [我要评价一下题目~]
提交日期: 2012-7-17 20:01:00
有效耗时: 1578毫秒
测试结果1: 通过本测试点|有效耗时172ms
测试结果2: 通过本测试点|有效耗时156ms
测试结果3: 通过本测试点|有效耗时156ms
测试结果4: 通过本测试点|有效耗时172ms
测试结果5: 通过本测试点|有效耗时172ms
测试结果6: 通过本测试点|有效耗时62ms
测试结果7: 通过本测试点|有效耗时172ms
测试结果8: 通过本测试点|有效耗时172ms
测试结果9: 通过本测试点|有效耗时172ms
测试结果10: 通过本测试点|有效耗时172ms
提交代码: view sourceprint?
01.const maxn=500;
02. maxm=500;
03.var f:array[0..maxn,0..maxm]of longint;
04. p:array[1..maxm,1..2]of longint;
05. a,sum:array[0..maxn]of longint;
06. i,j,k,m,temp,bk,next,loop,v,bg,now:longint;
07. flag:boolean;
08.function max(a,b:longint):longint;
09.begin
10. if a>b then exit(a) else exit(b);
11.end;
12.
13.function min(a,b:longint):longint;
14.begin
15. if a<b then exit(a) else exit(b);
16.end;
17.
18.
19.procedure printans(now,deep:longint);
20.begin
21. if deep>1 then printans(now-p[now,deep],deep-1);
22. writeln(now-p[now,deep]+1,' ',now);
23.
24.end;
25.
26.begin
27. readln(m,k);
28. fillchar(f,sizeof(f),0);
29. fillchar(a,sizeof(a),0);
30. fillchar(sum,sizeof(sum),0);
31. for i:= 1 to m do
32. f[i,0]:=maxlongint;
33. for i:=1 to m do
34. read(a[i]);
35. for i:=1 to m do
36. sum[i]:=sum[i-1]+a[i];
37. for i:=1 to m do
38. begin
39. loop:=min(k,i);
40. for v:=1 to loop do
41. begin
42. flag:=false;
43. next:=maxlongint;
44. for j:=1 to i-v+1 do
45. if not flag then
46. begin
47.
48. temp:=max(f[i-j,v-1],sum[i]-sum[i-j]);
49. if next>=temp then begin
50. next:=temp;
51. end;
52. end;
53. f[i,v]:=next;
54. end;
55. end;
56. // writeln(f[m,k]);
57. // printans(m,k);
58. bg:=m; now:=m; loop:=0;
59. while bg>=1 do begin
60. while (bg>=1)and(sum[bg]-sum[now-1]<=f[m,k])and(now>=1) do dec(now);
61. inc(loop);
62. p[loop,1]:=now+1;
63. p[loop,2]:=bg;
64. bg:=now;
65. end;
66. for i:=k downto 1 do
67.writeln(p[i,1],' ',p[i,2]);
68.
69.
70.end.