NOIP集训-10.17总结

水题一套
然而第三题我的算法貌似是错的(去掉暴力之后wa了一个点),然而考试时候还是莫名其妙的A掉了(还好拼了暴力...)
----------------------------------------------------------------------
Letter Game:SuperOj935
状态压缩DP
f(i,s)表示到了第i个串,s中为1的位对应的字符已经选了
 
状态转移:
f(i,s) = max{f(i+1,s),f(i+1,m(i,s)) + val(i)}
其中m(i,s)表示s这个状态下选上i个字符串之后的状态,如果不能选,则返回负无穷
val(i)表示第i个字符串的价值
 
----------------------------------------------------------------------
High Ways:SuperOj936
SB MST...
----------------------------------------------------------------------
Castle Protecting:SuperOj937
先离散化,按列号排序,列号一样的任意排
(假如一列有两个人,最优情况一定不会一列只选一个人,因此可以无视掉这种情况带来的影响)
 
考虑DP:f(i,j)表示到了第i个人,用了k个炸弹的最优解
状态转移:f(i,j) = min{f(p,j-1) + cost(p+1,i) | 1≤p<i}
cost(i,j)表示一个炸弹从第i个人炸到第j个人,最少的代价,可以n^2预处理出来
 
然后发现这个转移是n^3的,复杂度太高了,然后加了一个奇怪的优化:
打表发现当j相同时,不同的i的最优决策和i的值成正比
于是每一次就只需从i-1的最优决策开始枚举...
考试的时候小数据用暴力,大数据加上这个优化,A掉了,然后后来我去掉暴力之后发现有一个点WA掉了..
大概是错的吧..
----------------------------------------------------------------------