文档章节

POJ2373 - 单调队列

m2012
 m2012
发布于 2012/05/31 08:39
字数 779
阅读 377
收藏 0
这题的细节好多。。。。

首先,因为一个花丛区间是不能同时被两个木板覆盖的,所以,我们要把那些有交集的花丛区间都合并到一个花丛区间,这是第一步。

从这里开始,接下来,我们讨论中出现的“花丛区间”,都是指“合并以后的花丛区间“,也就是说,花丛区间之间是没有交集的,而且将它们按照左端点排序。设花丛区间数组为ranges[1...N]。

然后,我们把所有的合法点都标记出来,所谓的合法点x,是指:
如果存在某个花丛区间,使得x处于该花丛区间的中间区域(不包括两个端点),那么x是非法点。否则,x是合法点。

我们设f(i) 表示 用若干块木板合法地覆盖区间[0.....i]需要的最小的木板数目,而且i是合法点。所谓合法地覆盖,也就是说,每个花丛区间都被且只被一块木板覆盖。
看一下转移方程:
f(i) = min{ f(k) } + 1,  其中i - 2*b <= k <= i - 2*a     (#)
这个方程的含义是,为了得到f(i),我们要先算出前面的若干个f(k),且i - 2*b <= k <= i - 2*a。
而边界条件应该是f(0) = 0

由转移方程的形式,我们可以看出,这题可以用单调队列优化。
要注意的是,在方程(#)里,i和k,都肯定是偶数。


#include <algorithm>
#include <vector>
#include <deque>
#include <cstdio>
#include <cassert>
using namespace std;


#ifdef DEBUG
#define trace printf
#endif

template <class T1, class T2>
struct Tuple {
  T1 _1;
  T2 _2;
};

template <class T1, class T2>
Tuple<T1, T2> makeTuple(T1 t1, T2 t2) {  Tuple<T1, T2> r;  r._1 = t1;  r._2 = t2;  return r; }

typedef Tuple<int, int > TII;

bool lessTuple(const TII & a, const TII & b) {
	return a._1 < b._1;
}


const char TRUE = '\1';
const char FALSE = '\0';

char isValid[1000001];
deque<Tuple<int, int > > dQ;
deque<Tuple<int, int > > Q;
vector<Tuple<int, int> > ranges;
vector<Tuple<int, int> > combinedRanges;

int L, N, A, B;

void input() {
  scanf("%d %d", &N, &L);
  scanf("%d %d", &A, &B);
  int i;
  int S, E;
  ranges.clear();
  ranges.reserve(N);
  for (i = 0; i < N; ++i) {
    scanf("%d %d", &S, &E);
    ranges.push_back(makeTuple(S, E));
		// printf("@@ %d %d\n", ranges[ranges.size() - 1]._1, ranges[ranges.size() - 1]._2);
  }
}

void combine(const vector<Tuple<int, int > > & a, int len, vector<Tuple<int, int > > & res) {
  int i = 0;
  int j;

  while(1) {
    int start = a[i]._1;
    int end = a[i]._2;
    for (j = i + 1; j < len; ++j) {
      if (end <= a[j]._1 || a[j]._2 <= start) break;
      start = min(start, a[j]._1);
      end = max(end, a[j]._2);
    }
    res.push_back(makeTuple(start, end));
		// printf("*** %d %d\n", start, end);
    i = j;
    if (i >= len) break;
  }
}




void initValidLocations(vector<Tuple<int, int > > & a) {
  int i, j, k;
  for (i = 0; i <= 1000000; ++i) isValid[i] = TRUE;
  // assert(0);
  for (j = 0; j < a.size(); ++j) {
    // printf("@ %d %d\n", a[j]._1, a[j]._2);
    for (k = a[j]._1 + 1; k < a[j]._2; ++k) isValid[k] = FALSE;
  }
}


void deleteTheOld(int i) {
  while (!dQ.empty() && dQ.front()._1 < i) dQ.pop_front();
}

void insertTo(Tuple<int, int> x) {
  while(!dQ.empty() && dQ.back()._2 >= x._2) dQ.pop_back();
  dQ.push_back(x);
}



void dp() {
  int i;
  int a = A, b = B;
  int fi;

	bool existSolution = false;

	Q.push_back(makeTuple(0, 0));
  for (i = 2; i <= L; i+=2) {
    if (!isValid[i]) continue;

		while(!Q.empty() && Q.front()._1 <= i - 2 * a) {
			insertTo(Q.front());
			Q.pop_front();
		}

		deleteTheOld(i - 2 * b);

		if (!dQ.empty()) {
			fi = dQ.front()._2 + 1;
			Q.push_back(makeTuple(i, fi));
			if (i == L) existSolution = true;
		}
  }

  printf("%d\n", existSolution ? fi : -1);

}


int main() {
  input();
	sort(ranges.begin(), ranges.end(), lessTuple);
  combine(ranges, N, combinedRanges);
  initValidLocations(combinedRanges);
  // assert(0);
  dp();
  return 0;
}


© 著作权归作者所有

共有 人打赏支持
下一篇: 单调队列
m2012
粉丝 16
博文 129
码字总数 52548
作品 0
广州
程序员
私信 提问
12.8~12.9题解

今天主要写一下题解,总结待整理好后另开一篇发表(大约是明天)。 题面见各大OJ。本次题解都是讨论对于已经列好的DP方程的优化。 【HDU3401】 单调队列优化要求参数分离和枚举区间单调。对于...

myjs999
2017/12/10
0
0
12.9 省选训练总结3(2) DP的优化

目录 数据结构优化 维护前面的DP的最小最大值,使得不需要循环一边去找寻更新值。 滑窗 最重要的一种数据结构优化。维护一个最值单调双端队列,区间单调移动的时候只需要加入维护/弹出元素即...

OwenOwl
2017/12/10
0
0
dp优化 12 - 09

数据结构优化 单调队列优化 其中 双端队列队列,队列内保存之后可能成为最优值的值,保证有单调性。 特点是转移范围有限制。 真·数据结构优化 当 没有单调性时,就可以用线段树之类的数据结...

aziint
2017/12/10
0
0
栈与队列-单调栈,单调队列

什么时候使用? 单调栈 在均摊O(1) 即总时间复杂度为O(n)内实现找到某数右边第一个比它大(小)的数 单调队列 滑窗问题 在运行的过程中能够快速寻求前k个或后k个中最大或最小的值 我们直接来...

weixin_40777696
2017/12/13
0
0
DP优化的三种方法 单调队列优化 斜率优化 决策单调性优化

版权声明:myjs999原创文章 https://blog.csdn.net/myjs999/article/details/83478233 众所周知,DP优化有单调队列优化、斜率优化、矩阵快速幂优化、四边形不等式优化、数据结构优化等。本文...

myjs999
2018/10/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

gcc -lm -lpthread 一类的理解

C代码调用math.h中的函数有问题,如sqrt函数。会出现问题(点击看问题)。 原因是调用<math.h>中的函数,编译时需要链接对应的库 libm -lm命令是使编译的时候,链接数学库; -lptread 链接线...

shzwork
37分钟前
0
0
关于360插件化Replugin Activity动态修改父类的字节码操作

近期在接入360插件化方案Replugin时,发现出现崩溃情况。 大概崩溃内容如下: aused by: java.lang.ClassNotFoundException: Didn't find class "x.x.x.xActivity" on path: 我自己在插件代码......

Gemini-Lin
今天
1
0
mybatis缓存的装饰器模式

一般在开发生产中,对于新需求的实现,我们一般会有两种方式来处理,一种是直接修改已有组件的代码,另一种是使用继承方式。第一种显然会破坏已有组件的稳定性。第二种,会导致大量子类的出现...

算法之名
昨天
21
0
单元测试

右键方法 Go To --> Test,简便快速生成测试方法。 相关注解 @RunWith(SpringRunner.class) 表示要在测试环境中跑,底层实现是 jUnit测试工具。 @SpringBootTest 表示启动整个 Spring工程 @A...

imbiao
昨天
4
0
欧拉公式

欧拉公式表达式 欧拉公式的几何意 cosθ + j sinθ 是个复数,实数部分也就是实部为 cosθ ,虚数部分也就是虚部为 j sinθ ,对应复平面单位圆上的一个点。 根据欧拉公式和这个点可以用 复指...

sharelocked
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部