[CF797E] Array Queries（记忆化搜索，暴力）

题目链接：http://codeforces.com/contest/797/problem/E

题意：给n个数，q次询问。

每次询问给两个数p k，操作是p=ap+k，问多少次可以让p>n。

直接暴力会TLE，设计dp(i,j)为当p为i时，k为j时的最少步骤，可以这样更新来：dp(i+a(i)+j, j)=dp(i,j)+1。

显然n这么大，数组开不下。

这样，假如k很大的时候，p+ap+k是很容易超过n的，所以设定一个阈值，在这个阈值以外用暴力来做。其余的dp。

假如k大于500，那么暴力，小于500则dp。记忆化好写很多。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100100;
int n, q;
int a[maxn], dp[maxn][500];
int p, k;

int dfs(int p) {
    if(p > n) return 0;
    if(~dp[p][k]) return dp[p][k];
    return dp[p][k] = dfs(p+a[p]+k) + 1;
}

int main() {
    // freopen("in", "r", stdin);
    while(~scanf("%d",&n)) {
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        memset(dp, -1, sizeof(dp));
        scanf("%d", &q);
        while(q--) {
            scanf("%d%d",&p,&k);
            if(k > 500) {
                int ret = 0;
                while(p <= n) {
                    p = p + a[p] + k;
                    ret++;
                }
                printf("%d
", ret);
            }
            else printf("%d
", dfs(p));
        }
    }
    return 0;
}