program p1117;

var i,j,n,k:integer;

f:array [-5..200,0..6] of qword;

begin

readln(n,k);

f[1,1]:=1;

for i:=1 to n do

for j:=1 to k do

if not ((i=1) and (j=1)) then

f:=f+f;

writeln(f[n,k]);

end.

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|-

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

递推式f(n,k)=f(n-1,k-1)+f(n-k,k)。

上面的递推式比较好理解，为了拆出不同的解，我们只要拆分出的数排序后两两不同即可。每种拆分方案中，排序后最小的数为e，按照e的不同，我们可以把拆分方案分成2类：

e=1，我们把1除去，则剩余部分正好是n-1拆分成k-1部分，一共有f(n-1,k-1)个；

e>1，因为e是最小的数，所以所有的数都>1，我们把所有的数-1，则正好是n-k拆分成k部分，一共有f(n-k,k)个。

根据加法原理，得出以上递推式。

知道递推式后，就比较简单了，我们用动态规划的方法（如果直接递归，会有很多重复运算）。

920 ms 呵呵

一种莫名的冲动

交表

虽然较长

但更容易想明白

（第一次用DP做 竟然只有20分 太失望……）

交表 就是judge k

楼下的

g

是不是这出问题了

DP水平才差，写了个普通搜索

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 556ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：556ms

不剪枝的深度搜索就能AC......

上课时想出一种神奇的方法：）

search + cut treenode !

0 seonds!

总觉得有点错误，在研究了程序半天，觉得找不到错误。抱着试试的心态，结果直接AC。。。

PS：如果优化的好：前面的数〈=后面的数。以7，3为例，1+1+5合法，1+5+1不合法

0msAC

记忆化搜索

利用Ferrers那个旋转， 把数n分成k份的总拆分数，就等同于把n进行拆分，最大一份为k的所有拆分数

搜索都ac。。。无奈

搜索+剪枝+Vivid Puppy=AC

谈下我对这个公式的理解：

f[i][j]=f[j]+f[j-1];

f[i][j]就是i的j划分。

若划分出的一些数中有1，则把他拿掉，剩下的部分划分数就是f[j-1]。

若没有，就想像为每个部分都是一个柱子，都把最下面一层拿掉，上面剩下的划分数就是f[j]。

由于是在分类讨论，所以最后加起来^-^

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 759ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：784ms

穷举!!!非DP只递归

同楼上的大牛

dfs.......

16行就过了.

opt[n,k]=sigma f[n-k,t],1

这题正解是DP.但我对DP没什么感觉,况且这题也是弱数据,于是就搜....

数据很小,随便卡卡条件就可以过.

可恶啊，我用dfs只能过前四个,5555555

只好用DP...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms