关于小Y的作业的题解
2026-08-12 21:01:07
发布于：浙江
4阅读
0回复
0点赞
原题链接：
https://www.acgo.cn/problemset/info/138587?homeworkId=24024&teamCode=2042058713337094144
注意到题目要求：
abs(i-j)>max(Ai,Aj)
则对于Ai，可以到达的最大范围：i+Ai
则在i+Ai+1可以完成于i点的作业
同时，由于题目T<=1e4，n<=2e5，时间复杂度几乎直达O(n)
于是不难想到，该题使用DP
鉴于前面的思考，我们不难想到dp[i+Ai+1]+=a[i]
则DP实现如下：
vector<int> dp(n+1);
for(int i=1;i<=n;i++) dp[i]=a[i];
for(int i=1;i<=n;i++){
if(i+a[i]+1>n) continue;
dp[i+a[i]+1]+=a[i];
}
因此实现代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
int _;
cin>>_;
while(_--){
int n,ans=0;
cin>>n;
vector<int> a(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
vector<int> dp(n+1);
for(int i=1;i<=n;i++) dp[i]=a[i];
for(int i=1;i<=n;i++){
if(i+a[i]+1>n) continue;
dp[i+a[i]+1]+=a[i];
}for(int i=1;i<=n;i++){
ans=max(ans,dp[i]);
}cout<<ans<<endl;
}
return 0;
}
这里空空如也
有帮助，赞一个