## POJ2373 - 单调队列 原

m2012

f(i) = min{ f(k) } + 1,  其中i - 2*b <= k <= i - 2*a     （#）

``````#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

12.8~12.9题解

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

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

aziint
2017/12/10
0
0

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

myjs999
2018/10/28
0
0

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

shzwork
37分钟前
0
0

Gemini-Lin

1
0
mybatis缓存的装饰器模式

21
0

imbiao

4
0

sharelocked

5
0