本文主要是介绍Neko's loop(RMA+循环群)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem Description
Neko has a loop of size n.
The loop has a happy value ai on the i−th(0≤i≤n−1) grid.
Neko likes to jump on the loop.She can start at anywhere. If she stands at i−th grid, she will get ai happy value, and she can spend one unit energy to go to ((i+k)modn)−th grid. If she has already visited this grid, she can get happy value again. Neko can choose jump to next grid if she has energy or end at anywhere.
Neko has m unit energies and she wants to achieve at least s happy value.
How much happy value does she need at least before she jumps so that she can get at least s happy value? Please note that the happy value which neko has is a non-negative number initially, but it can become negative number when jumping.
Input
The first line contains only one integer T(T≤50), which indicates the number of test cases.
For each test case, the first line contains four integers n,s,m,k(1≤n≤104,1≤s≤1018,1≤m≤109,1≤k≤n).
The next line contains n integers, the i−th integer is ai−1(−109≤ai−1≤109)
Output
For each test case, output one line "Case #x: y", where x is the case number (starting from 1) and y is the answer.
Sample Input
2 3 10 5 2 3 2 1 5 20 6 3 2 3 2 1 5
Sample Output
Case #1: 0
Case #2: 2
思路：
在所有的数里面，根据他的规则就将数组分成了若干个循环圈。我们只要在每个圈里找出任意起点能获得的最大开心值，那么所有的开心值取个max，最后和s比较就行啦。既然是圈那么每跑一圈的收获都是确定的，那么我们就可以只计算余数就好了。
可是有这么一种情况，就是说我们要取得数比余数多但又小于一个周期。为了解决这么一个问题，我们可以把其中一个周期放到余数一起计算，这样就会得到最大值啦。然后RMQ来解决最大区间子段和。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int maxn = 1e5+666;
ll a[maxn],b[maxn],dp[maxn][20];
int mk[maxn];void ST(ll A[],ll n) {for (int i = 1; i <= n; i++)dp[i][0] = A[i];for (int j = 1; (1 << j) <= n; j++) {for (int i = 1; i + (1 << j) - 1 <= n; i++) {dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);}}
}
ll RMQ(int l, int r) {int k = (int)(log(double(r-l+1))/log((double)2));return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}int main()
{int t_t,cas = 1;scanf("%d",&t_t);while(t_t--){ll n,m,s,k;scanf("%lld%lld%lld%lld",&n,&s,&m,&k);;for(int i = 0; i < n; i++){scanf("%lld",&a[i]);}memset(mk,0,sizeof(mk));ll ans = -inf;for(int i = 0; i < n; i++){if(mk[i]) continue;int x = i;int j = 1;while(!mk[x]){mk[x] = 1;b[j++] = a[x];x = (x+k)%n;}for(int l = 1; l < j; l++){b[l+j-1] = b[l];b[l+2*j-2] = b[l];}b[0] = 0;for(int l = 1; l <= (j-1)*3; l++){b[l] += b[l-1];}ll res = 0;ll M = m;ll fasd = 0;if(m > j-1){M = m-j+1;fasd = j-1;}else M = m;ll mm = m%(j-1)+fasd;ST(b,(j-1)*3LL);ll mx = -inf;for(int l = 1; l < j; l++){ll mmx = 0;ll tmp = b[j-1];if(tmp > 0){mmx += tmp*(M/(j-1));}ll ghf = RMQ(l,l+mm-1)-b[l-1];mmx += ghf;mx = max(mx,mmx);}ans = max(ans,mx);}if(ans < 0) ans = s;else {if(s-ans >= 0) ans = s-ans;else ans = 0;}printf("Case #%d: %lld\n",cas++,ans);}return 0;
}/*
10
6 10 5 2
3 -3 2 3 -4 1*/
这篇关于Neko's loop(RMA+循环群)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
