讨论 / 动规其实真的能过
843279365 2012-07-17 05:09:00
点我顶贴 收藏 删除
状态: Accepted

测评机: 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.

查看更多回复
提交回复