Codeforces Round #278 (Div. 1) Strip RMQ
Alexandra has a paper strip with n numbers on it. Let's call them ai from left to right.
Now Alexandra wants to split it into some pieces (possibly 1). For each piece of strip, it must satisfy:
Please help Alexandra to find the minimal number of pieces meeting the condition above.
The first line contains three space-separated integers n, s, l (1 ≤ n ≤ 105, 0 ≤ s ≤ 109, 1 ≤ l ≤ 105).
The second line contains n integers ai separated by spaces ( - 109 ≤ ai ≤ 109).
Output the minimal number of strip pieces.
If there are no ways to split the strip, output -1.
7 2 2
1 3 1 2 4 1 2
3
7 2 2
1 100 1 100 1 100 1
-1
For the first sample, we can split the strip into 3 pieces: [1, 3, 1], [2, 4], [1, 2].
For the second sample, we can't let 1 and 100 be on the same piece, so no solution exists.
题目大意:让你把一个序列分几段,每段的最大值和最小值之差不超过s, 该段的长度也必须大于等于l,问你最少能分成几段?
这当题当然是要dp啦!反正我没想出来怎么划分。这题真是很棒!
首先给出dp公式 dp[i] = min{dp[j]+1, dp[i]}, i-j >= l && max{j+1~i}-min{j+1,~i}<= s
满足这个条件就可以dp了!用rmq求最大最小的差值, 双指针维护左右两个点i,j序列。
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; const int INF = 0x3f3f3f3f; int f[MAXN][20], g[MAXN][20], a[MAXN], dp[MAXN]; int n, q; void Rmq() { int lg = floor(log10(double(n))/log10(double(2))); for(int j = 1; j <= lg; ++j) { for(int i = 1; i <= n+1-(1<<j); ++i) { g[i][j] = max(g[i][j-1], g[i+(1<<(j-1))][j-1]); f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]); } } } int query(int a, int b) { int lg = floor(log10(double(b-a+1))/log10(double(2))); return max(g[a][lg], g[b-(1<<lg)+1][lg]) - min(f[a][lg], f[b-(1<<lg)+1][lg]); } int main() { int l, s; scanf("%d%d%d", &n, &s, &l); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); f[i][0] = g[i][0] = a[i]; dp[i] = INF; } Rmq(); dp[0] = 0; int pre = 0; for(int i = l; i <= n; i++) { while((i-pre >= l && query(pre+1, i) > s )|| dp[pre] == INF) pre++; printf("%d %d\n", pre, i); if(i - pre >= l) dp[i] = min(dp[pre]+1, dp[i]); } if(dp[n] == INF) printf("-1\n"); else printf("%d\n", dp[n]); return 0; }View Code 优质内容筛选与推荐>>