原来并非是我编程出了错,而是算法错了~
第三题我考虑得不周全,有想当然的成分,没有仔细想。后来把程序改了一下,就都对了。
我DP的方程搞错了:f(x)=max(child[x],(i in 1..child[x])f(x.ch[i])+1)
应该是:f(x)=max(child[x],(i in 1..child[x])(f(x.ch[i])<=f(x.ch[i+1]))f(x.ch[i])+i)
结果就导致了大部分第三题的点都是错的。
第四题属于题目看错(难道NOIP总是要拿一些容易混的题目来?去年这样,现在连模拟赛也这样?),其实一刀可以切一半的,这就是和NOI那道题目最大的不一样的地方~
成绩倒还可以~ 运气好~
Old Blog Link: http://computer.mblogger.cn/henryhu/posts/47059.aspx