首页 > 代码库 > codeforces 797 E. Array Queries【dp，暴力】
codeforces 797 E. Array Queries【dp，暴力】
题目链接：codeforces 797 E. Array Queries
题意：给你一个长度为n的数组a，和q个询问，每次询问为(p，k)，相应的把p转换为p+a[p]+k，直到p > n为止，求每次询问要转换的次数。
题解：纯暴力会TLE，所以在k为根号100000范围内dp打表
dp[i][j]表示初始p为i， k为j，需要转换几次可以大于n。
状态转移方程：dp[i][j] = dp[i+a[i]+j] + 1
#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int N = 1e5+5;const int M = 320+5;int dp[N][M];int a[N];int n, q;int main(){ int i, j; scanf("%d", &n); for(i = 1; i <= n; ++i) { scanf("%d", &a[i]); } memset(dp, 0, sizeof(dp)); for(i = n; i >= 1; --i) {//dp , 打表 for(j = 1; j <= M; ++j) { if(i + a[i] + j > n) dp[i][j] = 1; else { dp[i][j] = dp[i+a[i]+j][j] + 1; } } } scanf("%d", &q); while(q--) { int x, y; scanf("%d%d", &x, &y); if(y <= 320) printf("%d\n", dp[x][y]); else { int ans = 0; for(int p = x; p <= n; p += a[p]+y) ans++; printf("%d\n", ans); } } return 0;}
codeforces 797 E. Array Queries【dp，暴力】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。