讨论 / 既然大家只发代码,那我给个题解吧……
flysky126 2013-11-07 22:18:18
点我顶贴 收藏 删除
其实是个类似动归的思想

一开始不考虑删边,那么每个节点F[i][j]=F[i-1][j]+F[i][j-1]

初始化是F[i][0]=1,F[0][j]=1

然后考虑删边

如果删掉了(i,j)到(i+1,j)这条边,那么F[i+1][j]就变成了0,在F[i+1][j]这个点上造成的损失,将这个损失一直通过转移方程转移到F[n][m]那里,那么总的来说就会少掉F[i][j]*F[n-i][m-j]

类似的,如果删掉了(i,j)到(i,j+1)这条边,那么总的来说少掉F[i][j]*F[n-i][m-j]

以上需要注意边界

几个小提醒:

本人最开始CE了3次,才发现我的程序里写的是“ZZ0000007”,但是提交上去,这一段编译错误,给出的信息是“ZZ00000007”没有定义,也就是吞掉了我写的“%”等几个字符

然后用常量代替100000007,然后是“WA 20”,才发现本人虽然算出了总共有多少条边(也就是2*n*m+n+m),但是最后输出结果的时候用n代替了2*n*m+n+m……很是无语

然后修改了这一处,出现了“WA 40”,把测试数据弄出来才意识到严重的问题——虽然答案不会超过1000000007,但是中间的乘法过程有可能会超出32位整形,然后又调成了64位整形

然后又CE了

发现刚才调试的时候加的“system("pause");”没有去掉……

历经坎坷啊

查看更多回复
提交回复