Pro_6.pas 5.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184
  1. Program Pro_6; {例6的动态规划解法}
  2. Const Fin ='Input.txt'; {输入文件名}
  3. Fou ='Output.txt'; {输出文件名}
  4. Type Kus =Array[0..1160] Of Byte; {记录数组的类型说明}
  5. Zis =Array[0..1160] Of Integer;
  6. Var Ku :Array[1..1000] Of ^kus; {记录决策的数组}
  7. Shu,Shu1 :Array[1..1000] Of Byte;
  8. Zi :Array[0..1] Of Zis; {记录状态的数组}
  9. Use1 :Array[0..20,0..20,0..20] Of Integer; {记录三个数的组合的数组}
  10. Use2 :Array[0..1160,1..3] Of Byte; {将一个数转化为三个数组合的数组}
  11. Total,I,M,N,P,N1 :Integer;
  12. F :Text;
  13. W1,W2,W3,W4 :Word;
  14. {--Init--}
  15. Procedure Init; {初始化}
  16. Var I,J:Integer;
  17. Begin
  18. Assign(F,Fin);
  19. Reset(F);
  20. Readln(F,N1,M,P);
  21. For I:=1 To N1 Do
  22. Read(F,Shu1[I]);
  23. Shu[1]:=Shu1[1];
  24. N:=1;
  25. For I:=2 To N1 Do
  26. If Shu1[I]<>Shu1[I-1] Then
  27. Begin Inc(N);Shu[N]:=Shu1[I];End;
  28. Close(F);
  29. End;
  30. {---Diduse----}
  31. Procedure Diduse; {将三个数组合的情况转化为一个序数与其对应}
  32. Var Qs :Array[1..3] Of Byte;
  33. Stop :Byte;
  34. I,J,K :Byte;
  35. {==Serch==}
  36. Procedure Serch(Depth,From:Byte); {搜索所有的组合情况}
  37. Var I:Byte;
  38. Begin
  39. If Depth=Stop+1 Then
  40. Begin
  41. Inc(Total);
  42. Use2[Total,1]:=Qs[1];Use2[Total,2]:=Qs[2];
  43. Use2[Total,3]:=Qs[3];
  44. Use1[Qs[1],Qs[2],Qs[3]]:=Total;Use1[Qs[1],Qs[3],Qs[2]]:=Total;
  45. Use1[Qs[2],Qs[1],Qs[3]]:=Total;Use1[Qs[2],Qs[3],Qs[1]]:=Total;
  46. Use1[Qs[3],Qs[1],Qs[2]]:=Total;Use1[Qs[3],Qs[2],Qs[1]]:=Total;
  47. End
  48. Else
  49. For I:=From To M-1 Do
  50. Begin
  51. Qs[Depth]:=I;
  52. Serch(Depth+1,I+1);
  53. End;
  54. End;
  55. Begin
  56. Total:=0;
  57. Fillchar(Qs,Sizeof(Qs),0);
  58. For I:=0 To M Do
  59. For J:=0 To M Do
  60. For K:=0 To M Do
  61. Use1[I,J,K]:=-1;
  62. Use2[0,1]:=0;Use2[0,2]:=0;Use2[0,3]:=0;
  63. Use1[0,0,0]:=0;
  64. For Stop:=1 To P-1 Do
  65. Serch(1,1);
  66. End;
  67. {-----Main-------} {主过程}
  68. Procedure Main;
  69. Var I,J,K,W1,W2,W3 :Integer;
  70. Q :Array[1..4] Of Byte;
  71. Begin
  72. For I:=1 To N Do
  73. Begin New(Ku[I]);End;
  74. Fillchar(Zi,Sizeof(Zi),0); {动态规划初始化}
  75. Fillchar(Ku[1]^,Sizeof(Ku[1]^),0);
  76. Zi[0][0]:=1;
  77. Fillchar(Q,Sizeof(Q),0);
  78. For I:=2 To N Do {动态规划求值}
  79. Begin
  80. For J:=0 To Total Do
  81. If Zi[0][J]<>0 Then
  82. Begin
  83. W1:=0;
  84. For K:=1 To 3 Do
  85. Begin Q[K]:=Use2[J,K];
  86. If Q[K]>=Shu[I-1] Then Inc(Q[K]);
  87. If Q[K]=Shu[I] Then W1:=K;
  88. End;{End For K}
  89. Q[4]:=Shu[I-1];
  90. If W1<>0 Then
  91. Begin
  92. W2:=Q[4];Q[4]:=Q[W1];Q[W1]:=W2;
  93. For K:=1 To 3 Do
  94. If Q[K]>Shu[I] Then Dec(Q[K]);
  95. W3:=Use1[Q[1],Q[2],Q[3]];
  96. If (Zi[1][W3]=0) Or (Zi[1][W3]>Zi[0][J]) Then
  97. Begin
  98. Zi[1][W3]:=Zi[0][J];
  99. Ku[I]^[W3]:=Shu[I];
  100. End;
  101. End {End If}
  102. Else
  103. Begin
  104. For K:=1 To 4 Do
  105. If Q[K]>Shu[I] Then Dec(Q[K]);
  106. For K:=1 To 4 Do {分四种情况决策}
  107. Begin
  108. Case K Of
  109. 1:W1:=Use1[Q[2],Q[3],Q[4]];
  110. 2:W1:=Use1[Q[1],Q[3],Q[4]];
  111. 3:W1:=Use1[Q[1],Q[2],Q[4]];
  112. 4:W1:=Use1[Q[1],Q[2],Q[3]];
  113. End;
  114. If W1<>-1 Then
  115. If (Zi[1][W1]=0) Or (Zi[1][W1]>Zi[0][J]+1) Then
  116. Begin
  117. Zi[1][W1]:=Zi[0][J]+1;
  118. W2:=Q[K];
  119. If W2>=Shu[I] Then Inc(W2);
  120. Ku[I]^[W1]:=W2;
  121. End;{End If}
  122. End;{End For K}
  123. End;{End For Else};
  124. End;{End For J}
  125. Zi[0]:=Zi[1];
  126. Fillchar(Zi[1],Sizeof(Zi[1]),0);
  127. End;{End For I}
  128. End;
  129. {-----Print---}
  130. Procedure Print; {打印结果}
  131. Var Pr,Pr1 :Array[1..1000] Of Integer;
  132. Now,Q :Array[1..4] Of Byte;
  133. I,J,K,Ps,W1,W2 :Integer;
  134. Begin
  135. Ps:=1001;
  136. For J:=0 To Total Do
  137. If (Zi[0][J]<>0) And (Zi[0][J]<Ps) Then
  138. Begin Ps:=Zi[0][J];K:=J;End;
  139. Assign(F,Fou);
  140. Rewrite(F);
  141. Writeln(F,Ps);
  142. Now[2]:=Use2[K,1];
  143. Now[3]:=Use2[K,2];
  144. Now[4]:=Use2[K,3];
  145. For I:=2 To 4 Do
  146. If Now[I]>=Shu[N] Then Inc(Now[I]);
  147. Now[1]:=Shu[N];
  148. Pr[N]:=1;
  149. For K:=N-1 Downto 1 Do {分阶段打印}
  150. Begin
  151. J:=1;
  152. While Now[J]<>Shu[K+1] Do
  153. Inc(J);
  154. W2:=0;
  155. For I:=1 To 4 Do
  156. If I<>J Then
  157. Begin
  158. Inc(W2);Q[W2]:=Now[I];
  159. If Q[W2]>=Shu[K+1] Then Dec(Q[W2]);
  160. End;
  161. W1:=Use1[Q[1],Q[2],Q[3]];
  162. Now[J]:=Ku[K+1]^[W1];
  163. For I:=1 To 4 Do
  164. If Now[I]=Shu[K] Then
  165. Pr[K]:=I;
  166. End;{End For K}
  167. J:=1;
  168. Pr1[1]:=Pr[1];
  169. For I:=2 To N1 Do
  170. Begin
  171. If Shu1[I]<>Shu1[I-1] Then Inc(J);
  172. Pr1[I]:=Pr[J];
  173. End;
  174. For I:=1 To N1 Do
  175. Write(F,Pr1[I],' ');
  176. Close(F);
  177. End;
  178. {Main} {主程序}
  179. Begin
  180. Init; {初始化}
  181. Diduse; {准备}
  182. Main; {动态规划过程}
  183. Print; {输出}
  184. End.