End;
Writeln(f[M]); End.
C.求恰好装满的情况数。 Ahoi2001 Problem2
求自然数n本质不同的质数和的表达式的数目。
思路一,生成每个质数的系数的排列,在一一测试,这是通法。 procedure try(dep:integer); var i,j:integer; begin
cal; {此过程计算当前系数的计算结果,now为结果} if now>n then exit; {剪枝}
if dep=l+1 then begin {生成所有系数} cal;
if now=n then inc(tot); exit; end;
for i:=0 to n div pr[dep] do begin xs[dep]:=i; try(dep+1); xs[dep]:=0; end; end;
思路二,递归搜索效率较高 procedure try(dep,rest:integer); var i,j,x:integer; begin
if (rest<=0) or (dep=l+1) then begin if rest=0 then inc(tot); exit; end;
for i:=0 to rest div pr[dep] do try(dep+1,rest-pr[dep]*i); end;
{main: try(1,n); }
思路三:可使用动态规划求解 USACO1.2 money system
V个物品,背包容量为n,求放法总数。 转移方程:
Procedure update; var j,k:integer; begin c:=a;
for j:=0 to n do if a[j]>0 then
for k:=1 to n div now do
if j+now*k<=n then inc(c[j+now*k],a[j]); a:=c; end; {main} begin
read(now); {读入第一个物品的重量}
i:=0; {a为背包容量为i时的放法总数} while i<=n do begin
a:=1; inc(i,now); end; {定义第一个物品重的整数倍的重量a值为1,作为初值} for i:=2 to v do begin
read(now);
update; {动态更新} end;
writeln(a[n]);
四、排序算法 1.快速排序:
procedure qsort(l,r:integer); var i,j,mid:integer; begin
i:=l;j:=r; mid:=a[(l+r) div 2]; {将当前序列在中间位置的数定义为中间数} repeat
while a[i]
if i<=j then begin {若找到一组与排序目标不一致的数对则交换它们} t:=a[i]; a[i]:=a[j]; a[j]:=t; inc(i);dec(j); {继续找} end; until i>j;
if l B.插入排序: 思路:当前a[1]..a[i-1]已排好序了,现要插入a使a[1]..a有序。 procedure insert_sort; var i,j:integer; begin for i:=2 to n do begin a[0]:=a; j:=i-1;
相关推荐: