Codeforces Round #693 (Div. 3) C. Long Jumps
原題在這！
題目大意
? Polycarp在玩一個游戲，給定有n個元素的陣列a，設定一個起始點i，當 i <= n 時， i = i + a[i]，得分score = score + a[i]，試求出對于陣列a可以得出的最大得分，
決議
? 首先這道題資料量較大，時限2s，暴力求解是肯定⑧行的，
? 仔細觀察題目，對于每一個假定的起始值 i ，分為兩種情況：
-
i + a[i] > n ，這時其得分 ans = a[i]，
-
i + a[i] <= n ，這時游戲并未結束 i = i + a[i] , 得分ans += a[i] ，并進行下一輪，直到i + a[i] > n為止，
? 如果我們從 i = n 開始遍歷，并將a[i] 的得分儲存在 a[i] 中，即使出現 i + a[i] <= n的情況 ,其a[i+a[i]]的得分已經計算好，不需要從頭開始計算，
代碼如下
#include<bits/stdc++.h>
using namespace std;
const int N = 2*1e5+10;
int main(){
int t;
cin >> t;
for(int p = 0;p < t;p++){
long long a[N],n,maxn = 0;
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i = n;i > 0;i--){
if(i+a[i]<=n) a[i] += a[i+a[i]];
if(a[i] > maxn) maxn = a[i];
}
cout << maxn << endl;
}
return 0;
}
END
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/245281.html
標籤：其他
上一篇：【Leetcode每日筆記】877. 石子游戲/486. 預測贏家(Python)
下一篇：Python學習-小黑屋游戲