laekov

BZOJ3831 [Poi2014]Little Bird

一血yeah yeah。


第一眼觉得是比较麻烦的单调队列。


然后发现转移的时候只会加1或者不加。


那么取的时候只用取队首,队里首先fi单不降然后hi单减。那么一定没有方案比取队首差。


#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>


using namespace std;


int _d_; 

#define readInt(_x_) { \

int& _s_ = (_x_ = 0); \

while (!isdigit(_d_ = getchar())); \

while (_s_ = _s_ * 10 + _d_ - 48, isdigit(_d_ = getchar())); \

}


const int maxn = 1000009;


int n, m, a[maxn], f[maxn], q[maxn];


int getTrans(int l, int r) {

int v0 = f[q[l]];

while (l < r) {

int mid = (l + r + 1) >> 1;

if (f[q[mid]] == v0)

l = mid;

else

r = mid - 1;

}

return q[l];

}


int dp(int l) {

int hd = 0, tl = 1;

f[1] = 0;

q[0] = 1;

for (int i = 2; i <= n; ++ i) {

while (i - q[hd] > l)

++ hd;

int j = q[hd];

f[i] = f[j] + (a[i] >= a[j]);

while (hd < tl && (f[i] < f[q[tl - 1]] || (f[i] == f[q[tl - 1]] && a[i] >= a[q[tl - 1]])))

-- tl;

q[tl ++] = i;

}

return f[n];

}


int main() {

#ifndef ONLINE_JUDGE

//freopen("in.txt", "r", stdin);

#endif


readInt(n);

for (int i = 1; i <= n; ++ i)

readInt(a[i]);

readInt(m);

while (m --) {

int k;

readInt(k);

printf("%d\n", dp(k));

}

}


评论

© laekov | Powered by LOFTER