A题:Fight the Monster 枚举+二分
因为每个元素的数据范围只有100,所以可以用枚举,对于血量用二分,然后判断结果是否可行。
代码如下:
#include #include #include #include #include #include #include #include #include
B题: Strip 线段树+DP+二分(或窗口滑动)
这题做了好长时间。。。终于AC了。。
基本思路是DP。DP[i]表示从第一个到第i个的最小可划分的区间数。然后对于每个数,找到前面可到达的最左端L,对于L的查找可用二分法或者滑动窗口法进行枚举查找,判断当前枚举区间是否可行的时候用线段树对当前区间的最值进行查询。状态转移方程dp[i]=min(dp[L],....,dp[i-lenth])+1;然后对于dp[L]...dp[i-lenth]这段区间查最值可用另一棵线段树在logn的时间内查询。所以需要建两棵线段树。
话说最近换了代码风格。。看起来果然比以前的好看多了。。。
代码如下:
#include #include #include #include #include #include #include #include #include
声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。