NOIP集训-11.5总结

朱大神的题..
-------------------------------------------------------------------
 
寻路:SuperOjP1005
这道题似乎题目描述有问题...
如果没有问题的话就是很水的题了,直接按顺序插入建二叉搜索树就行
-------------------------------------------------------------------
恐狼前锋:SuperOjP1006
首先发现A数组是没有用的,最后加上A中所有数的和就行了
考虑DP:f[i][j]表示[i,j]这个区间杀完的最小代价
可以枚举这个区间内最后杀哪一个,于是有:
f[i][j] = min{f[i,k-1] + f[k+1,j] | i ≤ k ≤ j} + B[i-1] + B[j+1]
然后转移的顺序是先枚举长度,再枚举i
做完了,最后的答案就是f[1][n]
-------------------------------------------------------------------
序列问题:SuperOjP1007
考虑DP,设f[i][j]表示前i个数,是否已经空出了k个(j ∈{0,1}),最小长度
转移:f[i][0] = max{f[p][0] | p <= i-1}
      f[i][1] = max{ max{f[p][1] | p <= i-1} , max{f[p][0] | p <= i-k}}
然后以a[i]为下标,以f[i][j]为值,发现每一次转移其实就是一个区间最大值问题
建两棵线段树即可(分别代表j=1和0)
另外用这道题的方法可以以O(nlbn)的时间复杂度完成最长不下降子序列
-------------------------------------------------------------------