CF - 797E. Array Queries - dp+有选择地暴力

题目描述： E. Array Queries time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

a is an array of n positive integers, all of which are not greater than n.

You have to process q queries to this array. Each query is represented by two numbers p and k. Several operations are performed in each query; each operation changes p to p + ap + k. There operations are applied until p becomes greater than n. The answer to the query is the number of performed operations.

Input

The first line contains one integer n (1 ≤ n ≤ 100000).

The second line contains n integers — elements of a (1 ≤ ai ≤ n for each i from 1 to n).

The third line containts one integer q (1 ≤ q ≤ 100000).

Then q lines follow. Each line contains the values of p and k for corresponding query (1 ≤ p, k ≤ n).

Output

Print q integers, ith integer must be equal to the answer to ith query.

Example input 3 1 1 1 3 1 1 2 1 3 1 output 2 1 1 Note

Consider first example:

In first query after first operation p = 3, after second operation p = 5.

In next two queries p is greater than n after the first operation.

题意概述：给你一个n个元素的数组; 每个元素都在1..n之间; 然后给你q个询问; 每个询问由p和k构成; 会对p进行 p=p+a[p]+k操作若干次; 你要输出p第一次大于n之后操作了多少次; 解题思路：一种很好的想法是对于小于350的结果先计算出来，直接查询，大于350的结果再逐个dp。还有每次query的结果也可以放入dp内，以免下次继续查询。AC代码： #include <bits/stdc++.h> #define INF 0x3f3f3f3f #define maxn 100100 #define lson root << 1 #define rson root << 1 | 1 #define lent (t[root].r - t[root].l + 1) #define lenl (t[lson].r - t[lson].l + 1) #define lenr (t[rson].r - t[rson].l + 1) #define N 1111 #define eps 1e-6 #define pi acos(-1.0) #define e exp(1.0) using namespace std; const int mod = 1e9 + 7; typedef long long ll; typedef unsigned long long ull; int a[maxn], dp[maxn][350]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); long _begin_time = clock(); #endif int n; while (~scanf("%d", &n)) { for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = n; i >= 1; i--) for (int j = 1; j < 350; j++) { if (i + a[i] + j > n) dp[i][j] = 1; else dp[i][j] = dp[i + a[i] + j][j] + 1; } int q; scanf("%d", &q); while (q--) { int p, k; scanf("%d%d", &p, &k); if (k < 350) printf("%d\n", dp[p][k]); else { int cnt = 0; while (p <= n) { cnt++; p = p + a[p] + k; } printf("%d\n", cnt); } } } #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; }