我们用A[i,j]表示i个人分成j组的方法数,这样,显然要求i>=j*(j+1)/2;
但是A[i,j]该怎么算呢?我得到的方程是A[i,j]=所有的A[i-w*j,j-1]之和,
这里的同样要求(i-w*j)>=(j-1)*(j-1+1)/2
什么意思呢?w是什么呢?其实就是说我们给当前这一排(倒数第j排)安排w号人物,为了保证后面剩下的(j-1)排的人数都大于前面的每一排,我们就为他们每排预留w个人这就是从i里减去w*j的原因。这样,最终的结果就是A[n,2]+A[n,3]+A[n,4]+...+A[n,x],这里的x是满足
(x+1)*x/2<=n 的最大整数(很可耻的是,只有一排的情况居然不算一种方法,这太不符合逻辑了,幸好我尝试了题目所给的测试数据)
一下是pascal代码:
var count,j,i,n:longint;
a:array[1..130,1..100] of longint;
function work(i,j:longint):longint;
var t,w:longint;
begin
if not(j*(j+1)<=i*2) then exit(0);
if j=1 then exit(1);
t:=0;
w:=1;
if a[i,j]<>-1 then exit(a[i,j]);
while (2*(i-w*j)>=(j-1)*j)and(j>=2) do begin inc(t,work(i-w*j,j-1));inc(w);end;
a[i,j]:=t;
work:=t;
end;
begin
readln(n);
for i:=1 to 130 do
for j:=1 to 100 do a[i,j]:=-1;
j:=2;
while (j+1)*j<=n*2 do begin inc(count,work(n,j));inc(j);end;
writeln(count);
end.
顺便问一下大牛们,在pascal里程序名有什么实际的用途么?只从我开始搞程序,我就从来没写过程序名,貌似也没遭受什么灾难啊!
function f(x,m:longint):longint;
var i,t:longint;
begin
if (m+1) div 2-1<=x then
begin
f:=1;
exit;
end;
t:=0;
for i:=x+1 to (m+1) div 2-1 do
t:=t+f(i,m-i);
f:=t+1;
end;
设S为方案总数,
S=∑P(N,I) (2<=I<=N)
相当于
S=P(N,2)+P(N,3)+...+P(N,N)
P(N,K)意思就是“正整数N的K分拆”,但不允许重复项(例如,5=1+1+3)
公式 P(N,K)=P(N-K,K)+P(N-K,K-1)
IF K=1 THEN P(N,K)=1
IF N<=K THEN P(N,K)=0