讨论 / 题73算法分析(包含代码)
3144046cjc 2011-02-26 05:58:00
点我顶贴 收藏 删除
最初我以为这样熟悉的情景应该包含公式,但是懒得去推,直接用转移方程搞定。

我们用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里程序名有什么实际的用途么?只从我开始搞程序,我就从来没写过程序名,貌似也没遭受什么灾难啊!

#1 姚斯宇8888@2008-02-15 07:53:00
回复 删除
太感谢了

好心的牛啊, 终于有思路了……

#2 不做寻常人@2008-02-15 16:36:00
回复 删除
还是看不懂.......

不过同样拜谢了大牛.......

我以后再来观摩.............

#3 ssxyh@2008-02-15 17:54:00
回复 删除
你写的这确实是递推,状态转移是要有决策的,有判断,显然不是动态规划...吓我...不过思路很好!借鉴下.
#4 ssxyh@2008-02-15 18:30:00
回复 删除
很好,很强大!!!!~
#5 gaoxin@2008-02-16 19:03:00
回复 删除
ms和我的思路一样,我的好象简单点

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;

#6 wxfred@2008-03-25 06:46:00
回复 删除
这道题与正整数N的K分拆有相似之处,只不过此题多了些附加要求。(不了解“正整数N的K分拆”的,建议去看一看基本思路)。

设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

#7 霖~@2011-02-26 05:58:00
回复 删除
Orz
查看更多回复
提交回复