题目描述

给定两个包含n nn个整数的数组a = [ a 1 , … , a n ] a=[a_1,\dots,a_n]a=[a1​,…,an​]与b = [ b 1 , … , b n ] b=[b_1,\dots,b_n]b=[b1​,…,bn​]。你需要指定若干下标p 1 < ⋯ < p k p_1\lt \cdots\lt p_kp1​<⋯<pk​（1 ≤ k ≤ n 1\leq k\leq n1≤k≤n）使得以下条件成立：

• 1 ≤ p i ≤ n 1\leq p_i\leq n1≤pi​≤n（1 ≤ i ≤ k 1\leq i\leq k1≤i≤k）；
• p i + 1 ≥ p i + b p i p_{i+1}\geq p_i+b_{p_i}pi+1​≥pi​+bpi​​（1 ≤ i < k 1\leq i< k1≤i<k）。

你需要在满足以上条件的前提下最大化∑ i = 1 k a p i \sum_{i=1}^k a_{p_i}∑i=1k​api​​，也即最大化数组a aa对应下标的整数之和。

输入格式

第一行，一个正整数n nn，表示数组长度。

第二行，n nn个正整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1​,a2​,…,an​，表示数组a aa。

第三行，n nn个正整数b 1 , b 2 , … , b n b_1,b_2,\dots,b_nb1​,b2​,…,bn​，表示数组b bb。

输出格式

一行，一个整数，表示在满足下标条件的前提下，数组a aa对应下标的整数之和的最大值。

输入输出样例 #1

输入 #1

4 1 2 3 4 3 3 1 1

输出 #1

7

输入输出样例 #2

输入 #2

6 1 1 4 5 1 4 1 2 3 2 1 0

输出 #2

11

说明/提示

对于40 % 40\%40%的测试点，保证2 ≤ n ≤ 10 3 2\leq n\leq 10^32≤n≤103。

对于所有测试点，保证2 ≤ n ≤ 10 5 2\leq n\leq 10^52≤n≤105，0 ≤ a i ≤ 10 9 0\leq a_i\leq 10^90≤ai​≤109，0 ≤ b i ≤ n 0\leq b_i\leq n0≤bi​≤n。

思路&解法

他给你了三个数组a = [ a 1 , … , a n ] a=[a_1,\dots,a_n]a=[a1​,…,an​]、b = [ b 1 , … , b n ] b=[b_1,\dots,b_n]b=[b1​,…,bn​]和p [ p 1 , … , p k ] p[p_1,\dots,p_k]p[p1​,…,pk​]。
他要让p pp满足以下条件
{ 1 ≤ p i ≤ n 1 ≤ i ≤ k p i + 1 ≥ p i + b p i 1 ≤ i < k \begin{cases} 1\leq p_i\leq n & 1\leq i\leq k\\ p_{i+1}\geq p_i+b_{p_i} & 1\leq i < k\\ \end{cases}{1≤pi​≤npi+1​≥pi​+bpi​​​1≤i≤k1≤i<k​
把p pp的各个位置想象成并排的小房子且里面都装了安防系统在p i + b p i − 1 p_i + b_{p_i} -1pi​+bpi​​−1以内的地方偷了会报警
a aa是每家有多少钱
我最多可以偷多少钱（不触发报警系统）

分析到这里这就很像Leetcode的这道题
这也告诉我们这道题是 dp。
还有一个要注意的点：dp要开l o n g l o n g long longlonglong，不开见祖宗！

AC CODE:

#include<bits/stdc++.h>usingnamespacestd;longlongdp[int(1e5+5)];longlonga[int(1e5+5)];longlongb[int(1e5+5)];intmain(){intn;cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}for(inti=1;i<=n;i++){cin>>b[i];}longlongans=0;for(inti=1;i<=n;i++){ans=max(ans,dp[i]+a[i]);if(i+b[i]<=n)dp[i+b[i]]=max(dp[i+b[i]],dp[i]+a[i]);dp[i+1]=max(dp[i+1],dp[i]);}cout<<ans;}

详情