切换到宽版
发帖 回复
返回列表
12345
  • 32978阅读
  • 49回复

NOIP2006提高组满分源代码 [复制链接]

 上一主题 下一主题
离线archimedes
管理员
 
只看楼主 倒序阅读 0 发表于: 2006-11-19
— 本帖被 archimedes 执行取消置顶操作(2007-07-16) —
NOIP2006提高组满分源代码

注：来源: www.oiers.cn
energy：

复制代码
  1. {
  2. Problem: Noip 2006 Problem 1
  3. Algorithm: Dynamic Programming
  4. }
  5. const
  6. maxn = 100;
  7. var
  8. n, i, j, k, p, ans:longint;
  9. data:array[1..maxn,1..2] of longint;
  10. dp:array[1..maxn,1..maxn] of longint;
  12. function max(a, b:longint):longint;
  13. begin
  14. if a > b then max:=a else max:=b;
  15. end;
  17. begin
  18. assign(input,'energy.in');
  19. reset(input);
  20. assign(output,'energy.out');
  21. rewrite(output);
  23. { input }
  24. read(n);
  25. for i:=1 to n do read(data[i, 1]);
  27. { Main }
  28. data[n, 2]:=data[1, 1];
  29. for i:=1 to n - 1 do data[i, 2]:=data[i+1, 1];
  31. fillchar(dp, sizeof(dp), 0);
  32. for p:=1 to n-1 do
  33.   for i:=1 to n do
  34.   begin
  35.     j:=(i + p - 1) mod n + 1;
  36.     if i < j then
  37.     begin
  38.     for k:=i to j-1 do
  39.       dp[i, j]:=max(dp[i, j], dp[i, k] + dp[k+1, j] +
  40.         data[i, 1] * data[k, 2] * data[j, 2]);
  41.     end;
  43.     if i > j then
  44.     begin
  45.     for k:=i to n-1 do
  46.       dp[i, j]:=max(dp[i, j], dp[i, k] + dp[k+1, j] +
  47.         data[i, 1] * data[k, 2] * data[j, 2]);
  49.     dp[i, j]:=max(dp[i, j], dp[i, n] + dp[1, j] +
  50.       data[i, 1] * data[n, 2] * data[j, 2]);
  52.     for k:=1 to j-1 do
  53.       dp[i, j]:=max(dp[i, j], dp[i, k] + dp[k+1, j] +
  54.         data[i, 1] * data[k, 2] * data[j, 2]);
  55.     end;
  56.   end;
  58. { output }
  59. ans:=-1;
  60. for i:=1 to n do
  61. begin
  62.   j:=(i + n - 2) mod n + 1;
  63.   ans:=max(ans, dp[i, j]);
  64. end;
  65. writeln(ans);
  67. close(input);
  68. close(output);
  69. end.


JSP：




复制代码
  1. {
  2. Problem: Noip 2006 Problem 3
  3. Algorithm: Simulation
  4. }
  5. const
  6. maxn = 20;
  7. maxm = 20;
  8. maxs = 5000;
  9. type
  10. Tseq = record
  11.       st, ed:longint;
  12.       end;
  13. var
  14. n, m, i, j, k, ans:longint;
  15. ma, tim, x, y:longint;
  16. t:array[1..maxn] of longint;
  17. data, a:array[1..maxn*maxm] of longint;
  18. num:array[1..maxn,1..maxm] of longint;
  19. time:array[1..maxn,1..maxm] of longint;
  20. free:array[1..maxm,1..maxs] of Tseq;
  21. count:array[1..maxm] of longint;
  22. last:array[1..maxn] of longint;
  24. function max(a, b:longint):longint;
  25. begin
  26. if a > b then max:=a else max:=b;
  27. end;
  29. function find_free(k, ma, tim:longint; var x, y:longint):longint;
  30. var
  31. i, minx, best:longint;
  32. begin
  33. minx:=maxlongint;
  34. for i:=1 to count[ma] do
  35.   if free[ma, i].ed - free[ma, i].st >= tim then
  36.     if last[k] <= free[ma, i].st then
  37.     begin
  38.     if free[ma, i].st < minx then
  39.     begin
  40.       minx:=free[ma, i].st;
  41.       best:=i;
  42.     end;
  43.     end else
  44.     if (last[k] > free[ma, i].st) and (last[k] + tim <= free[ma, i].ed) then
  45.     begin
  46.     if last[k] < minx then
  47.     begin
  48.       minx:=last[k];
  49.       best:=i;
  50.     end;
  51.     end;
  53. find_free:=best;
  54. x:=minx;
  55. y:=x + tim;
  56. end;
  58. begin
  59. assign(input,'jsp.in');
  60. reset(input);
  61. assign(output,'jsp.out');
  62. rewrite(output);
  64. { input }
  65. read(m, n);
  66. for i:=1 to m * n do read(data[i]);
  67. for i:=1 to n do
  68.   for j:=1 to m do read(num[i, j]);
  69. for i:=1 to n do
  70.   for j:=1 to m do read(time[i, j]);
  72. { Main }
  73. fillchar(t, sizeof(t), 0);
  74. for i:=1 to n * m do
  75. begin
  76.   inc(t[data[i]]);
  77.   a[i]:=t[data[i]];
  78. end;
  80. fillchar(last, sizeof(last), 0);
  81. for i:=1 to m do
  82. begin
  83.   count[i]:=1;
  84.   free[i, 1].st:=0;
  85.   free[i, 1].ed:=maxlongint;
  86. end;
  88. for i:=1 to n * m do
  89. begin
  90.   ma:=num[data[i], a[i]];
  91.   tim:=time[data[i], a[i]];
  92.   k:=find_free(data[i], ma, tim, x, y);
  94.   inc(count[ma]);
  95.   free[ma, count[ma]].st:=y;
  96.   free[ma, count[ma]].ed:=free[ma, k].ed;
  97.   free[ma, k].ed:=x;
  99.   last[data[i]]:=y;
  100. end;
  102. { output }
  103. ans:=-1;
  104. for i:=1 to m do
  105.   for j:=1 to count[i] do
  106.     if free[i, j].ed = maxlongint then
  107.     ans:=max(ans, free[i, j].st);
  108. writeln(ans);
  110. close(input);
  111. close(output);
  112. end.


budget：




复制代码
  1. {
  2. Problem: Noip 2006 Problem 2
  3. Algorithm: Dynamic Programming
  4. }
  7. const
  8. maxm = 61;
  9. maxn = 32000;
  10. var
  11. n, m, i, j, k, ans:longint;
  12. cost, p, q, cost_tmp, p_tmp:array[1..maxm] of longint;
  13. data:array[1..maxm] of longint;
  14. flag:array[1..maxm] of byte;
  15. dp:array[1..maxm+1,-1..2,0..maxn] of longint;
  17. function max(a, b:longint):longint;
  18. begin
  19. if a > b then max:=a else max:=b;
  20. end;
  22. begin
  23. assign(input,'budget.in');
  24. reset(input);
  25. assign(output,'budget.out');
  26. rewrite(output);
  28. { input }
  29. read(n, m);
  30. for i:=1 to m do
  31.   read(cost[i], p[i], q[i]);
  33. { Main }
  34. k:=0;
  35. for i:=1 to m do
  36.   if q[i] = 0 then
  37.   begin
  38.     inc(k);
  39.     data[k]:=i;
  40.     flag[k]:=1;
  41.     for j:=1 to m do
  42.     if q[j] = i then
  43.     begin
  44.       inc(k);
  45.       data[k]:=j;
  46.       flag[k]:=0;
  47.     end;
  48.   end;
  50. // huan yuan cost
  51. for i:=1 to m do
  52. begin
  53.   cost_tmp[i]:=cost[data[i]];
  54.   p_tmp[i]:=p[data[i]];
  55. end;
  56. cost:=cost_tmp;
  57. p:=p_tmp;
  59. for i:=1 to m+1 do
  60.   for j:=-1 to 2 do
  61.     for k:=0 to n do
  62.     dp[i, j, k]:=-1;
  64. dp[1, -1, 0]:=0;
  65. for i:=1 to m do
  66.   for k:=0 to N do
  67.   begin
  68.     if flag[i] = 1 then
  69.     begin
  70.     for j:=-1 to 2 do
  71.     begin
  72.       if dp[i, j, k] = -1 then continue;
  73.       if k + cost[i] <= n then
  74.         dp[i+1, 0, k+cost[i]]:=max(dp[i+1, 0, k+cost[i]], dp[i, j, k] + cost[i] * p[i]);
  76.       dp[i+1, -1, k]:=max(dp[i+1, -1, k], dp[i, j, k]);
  77.     end;
  78.     end;
  80.     if flag[i] = 0 then
  81.     begin
  82.     for j:=-1 to 2 do
  83.     begin
  84.       if dp[i, j, k] = -1 then continue;
  85.       case j of
  86.       -1   : dp[i+1, j, k]:=max(dp[i+1, j, k], dp[i, j, k]);
  87.       0, 1 : begin
  88.               if k + cost[i] <= n then
  89.               dp[i+1, j+1, k+cost[i]]:=max(dp[i+1, j+1, k+cost[i]], dp[i, j, k] + cost[i] * p[i]);
  91.               dp[i+1, j, k]:=max(dp[i+1, j, k], dp[i, j, k]);
  92.             end;
  93.       2   : dp[i+1, j, k]:=max(dp[i+1, j, k], dp[i, j, k]);
  94.       end;
  95.     end;
  96.     end;
  97.   end;
  99. { output }
  100. ans:=0;
  101. for j:=-1 to 2 do
  102.   for k:=0 to n do
  103.     ans:=max(ans, dp[m+1, j, k]);
  104. writeln(ans);
  106. close(input);
  107. close(output);
  108. end.


digital




复制代码
  1. const inf               ='digital.in';
  2.     ouf               ='digital.out';
  3.     maxn               =512;
  4.     pw                 :array[1..9]of longint=(2,4,8,16,32,64,128,256,512);
  5.     mol               =1000000;
  7. type bignum             =array[0..50]of longint;
  9. var   k,w,n,i,p,j           :longint;
  10.     f                 :array[boolean,0..maxn]of bignum;
  11.     ans               :bignum;
  13. procedure init;
  14. begin
  15.   assign(input,inf);
  16.   reset(input);
  17.   readln(k,w);
  18.   n:=1;
  19.   for i:=1 to k do
  20.   n:=n*2;
  21.   close(input);
  22. end;
  24. procedure hiadd(var a,b:bignum);
  25. var i,j,n,tmp             :longint;
  26.   ta                 :bignum;
  27. begin
  28.   if a[0]<b[0] then a[0]:=b[0];
  29.   for i:=1 to a[0] do
  30.   a[i]:=a[i]+b[i];
  31.   for i:=1 to a[0] do
  32.   begin
  33.     tmp:=a[i] div mol; inc(a[i+1],tmp);
  34.     a[i]:=a[i] mod mol;
  35.   end;
  36.   if a[a[0]+1]>0 then inc(a[0]);
  37. end;
  39. procedure cal;
  40. var     now,last     :boolean;
  41.       change     :boolean;
  42.       max       :longint;
  44. begin
  45.   p:=k;
  46.   now:=true; last:=false;
  47.   fillchar(f,sizeof(f),0);
  48.   for i:=0 to n do
  49.   begin
  50.     f[now,i][0]:=1; f[now,i][1]:=1;
  51.   end;
  52.   dec(n);
  53.   if w>k*n then w:=k*n;
  54.   ans[0]:=1; ans[1]:=0;
  55.   repeat
  56.   now:=not now; last:=not last;
  57.   fillchar(f[now],sizeof(f[now]),0);
  58.   change:=false;
  59.   inc(p,k);
  60.   if p>w then
  61.     begin
  62.     dec(p,k); max:=w-p; p:=w;
  63.     end
  64.   else max:=k;
  65.   hiadd(f[now,n-1],f[last,n]);
  66.   for i:=n-2 downto 0 do
  67.     begin
  68.       f[now,i]:=f[now,i+1];
  69.       hiadd(f[now,i],f[last,i+1]);
  70.     end;
  71.   if p>2*k then hiadd(ans,f[now,0]);
  72.   until p=w;
  73.   for i:=1 to pw[max]-1 do
  74.   hiadd(ans,f[now,i]);
  75.   assign(output,ouf);
  76.   rewrite(output);
  77.   n:=ans[0];
  78.   write(ans[n]);
  79.   for i:=n-1 downto 1 do
  80.   begin
  81.     max:=mol div 10;
  82.     while max<>0 do
  83.     begin
  84.       write(ans[i] div max mod 10);
  85.       max:=max div 10;
  86.     end;
  87.   end;
  88.   writeln;
  89.   close(output);
  90. end;
  92. begin
  93. init; cal;
  94. end.
[ 此贴被sammy312在2006-11-25 09:52重新编辑 ]
回复
举报
分享到 淘江湖 新浪 QQ微博 QQ空间 开心 人人 豆瓣 网易微博 百度 鲜果 白社会 飞信
离线morethan
OIFans入门选手
只看该作者 1 发表于: 2006-11-20
楼主辛苦，谢了！
已收藏！
回复
举报
离线76363723
OIFans入门选手
只看该作者 2 发表于: 2006-11-22
这是今年复赛的答案吗.?
回复
举报
离线76363723
OIFans入门选手
只看该作者 3 发表于: 2006-11-22
本部分内容设定了隐藏，需要回复后才能看到
回复
举报
离线lhzb
OIFans入门选手
只看该作者 4 发表于: 2006-11-22
请问有没有C的
回复
举报
离线lhzb
OIFans入门选手
只看该作者 5 发表于: 2006-11-22
请问有没有C的
回复
举报
离线wolf
OIFans入门选手
只看该作者 6 发表于: 2006-11-22
我要普及的!!!
回复
举报
离线liuyinsitan
OIFans入门选手
只看该作者 7 发表于: 2006-11-23
顶一下
回复
举报
离线网络虾客
OIFans入门选手
只看该作者 8 发表于: 2006-11-23
拜托,,,,从我那copy的也写个......来源....
回复
举报
离线solomonw
OIFans入门选手
只看该作者 9 发表于: 2006-11-24
copy的?
回复
举报
发帖 回复
返回列表
12345
快速回复
限100 字节
 
上一个 下一个