首页 > 代码库 > BZOJ1197 [HNOI2006]花仙子的魔法
BZOJ1197 [HNOI2006]花仙子的魔法
其实是一道奇怪的DP题，蒟蒻又不会做。。。
看了Vfk的题解才算弄明白是怎么一回事：
令f[i, j]表示i维有j个球时最大切割部分，则
f[i, j] = f[i, j - 1] + f[i - 1, j - 1]
其中第一部分很好理解，就是前j - 1个球的最大个数，然后就是第二部分的理解：
j - 1个球后再加一个球，于是最优的情况就是最后一个球与前j - 1个球都相交
而求面试i - 1维的，相交出来的是i - 2维空间 <=> i - 1维空间用j - 1个i - 2个球划分的最优个数。
证毕。。。
1 /************************************************************** 2 Problem: 1197 3 User: rausen 4 Language: Pascal 5 Result: Accepted 6 Time:0 ms 7 Memory:264 kb 8 ****************************************************************/ 9 10 var11 n, m : longint;12 f : array[0..20, 0..200] of int64;13 cal : array[0..20, 0..200] of boolean;14 15 procedure pre_work;16 var17 i, j : longint;18 19 begin20 for i := 1 to n do begin21 f[i, 1] := 2;22 cal[i, 1] := true;23 end;24 for j := 1 to m do begin25 f[1, j] := 2 * j;26 cal[1, j] := true;27 end;28 end;29 30 function calc(x, y : longint) : int64;31 begin32 if cal[x, y] then exit(f[x, y]);33 cal[x, y] := true;34 f[x, y] := calc(x - 1, y - 1) + calc(x, y - 1);35 exit(f[x, y]);36 end;37 38 begin39 readln(m, n);40 fillchar(cal, sizeof(cal), false);41 pre_work;42 writeln(calc(n, m));43 end.
（p.s. 程序是P的不要怪我>.<。。。是以前写的。。。！）
BZOJ1197 [HNOI2006]花仙子的魔法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。