245 条题解
-
0xuketian LV 9 @ 2007-07-26 11:47:05
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)个。
根据加法原理,得出以上递推式。
知道递推式后,就比较简单了,我们用动态规划的方法(如果直接递归,会有很多重复运算)。
-
02007-07-23 15:54:47@
920 ms 呵呵
-
02007-07-16 16:50:01@
一种莫名的冲动
交表
虽然较长
但更容易想明白
(第一次用DP做 竟然只有20分 太失望……)
交表 就是judge k -
02007-06-02 20:06:35@
楼下的
g
是不是这出问题了 -
02007-05-20 12:54:30@
DP水平才差,写了个普通搜索
-
02007-05-18 11:40:18@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 556ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:556ms
不剪枝的深度搜索就能AC...... -
02007-04-05 17:32:44@
上课时想出一种神奇的方法:)
-
02007-03-30 00:12:39@
search + cut treenode !
0 seonds! -
02007-03-27 19:09:01@
总觉得有点错误,在研究了程序半天,觉得找不到错误。抱着试试的心态,结果直接AC。。。
PS:如果优化的好:前面的数〈=后面的数。以7,3为例,1+1+5合法,1+5+1不合法
0msAC -
02006-12-11 16:00:08@
记忆化搜索
利用Ferrers那个旋转, 把数n分成k份的总拆分数,就等同于把n进行拆分,最大一份为k的所有拆分数 -
02006-12-11 11:19:22@
搜索都ac。。。无奈
-
02006-12-02 22:28:51@
搜索+剪枝+Vivid Puppy=AC
-
02006-11-16 09:19:27@
谈下我对这个公式的理解:
f[i][j]=f[j]+f[j-1];f[i][j]就是i的j划分。
若划分出的一些数中有1,则把他拿掉,剩下的部分划分数就是f[j-1]。若没有,就想像为每个部分都是一个柱子,都把最下面一层拿掉,上面剩下的划分数就是f[j]。
由于是在分类讨论,所以最后加起来^-^
-
02006-11-15 19:22:07@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 25ms
├ 测试数据 05:答案正确... 759ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:784ms
穷举!!!非DP只递归 -
02008-09-27 21:47:52@
同楼上的大牛
-
02006-11-09 23:27:08@
dfs.......
-
02006-10-30 15:51:48@
16行就过了.
opt[n,k]=sigma f[n-k,t],1
-
02006-10-29 03:07:41@
这题正解是DP.但我对DP没什么感觉,况且这题也是弱数据,于是就搜....
数据很小,随便卡卡条件就可以过.
-
02006-10-07 15:31:02@
可恶啊,我用dfs只能过前四个,5555555
只好用DP...
-
02006-10-07 12:35:11@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms