http://acm.hdu.edu.cn/showproblem.php?pid=6444
题意
一个有n个数的环，每次循环走k步，走到每个点都有具体的权值，问在任意点出发最多走m步的情况下，一开始需要拥有多少价值才能使最终总价值不少于s。
分析
对于一个环，固定步数下是有循环节的，不同循环节内的节点各不相同，根据裴蜀定理可得每个循环节的长度为 n / gcd(n, k)，所以共有 gcd(n, k) 个循环节。
暴力把这些循环节找出来。
对于每个循环节，假设循环节长度为sz
①m%sz==0
此时能走整个周期，但是为了最后的值最大，先走m/sz-1圈，最后一拳走最大的一段，即求长度最大为sz的最大子段和。因为整个周期的值可能为负，所以取max（sum，0）
②m%sz≠0
这个情况下走完整数周期后还剩下m%sz步，同理，求长度最大为m%sz的最大子段和。
最后，两者取最优。
至于求最大子段和，则用单调队列来处理。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define eps 0.0000000001
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define random(a, b) rand()*rand()%(b-a+1)+a
#define pi acos(-1)
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
const int maxn = + ;
const int maxm = + ;
const int mod = 1e9+;
ll n,m,s,k;
vector<ll> vec;
ll a[maxn],q[maxn],stk[maxn],sum[maxn];
bool vis[maxn]; ll cal(vector<ll> &v,ll tmp){
ll res=;
ll nn=v.size();
ll he=,ta=;
for(ll i=;i<nn;i++) q[i+nn]=q[i]=a[v[i]];
nn*=;
for(ll i=;i<nn;i++){
if(i==) sum[i]=q[i];
else sum[i]=sum[i-]+q[i];
if(i<tmp) res=max(res,sum[i]);
while(he<ta&&stk[he]+tmp<i) he++;
if(he<ta) res=max(res,sum[i]-sum[stk[he]]);
while(he<ta&&sum[stk[ta-]]>=sum[i]) ta--;
stk[ta++]=i;
}
return res;
}
ll solve(vector<ll>&v){
ll sz=v.size();
ll sm=;
for(ll i=;i<sz;i++) sm+=a[v[i]];
ll len1=m/sz,len2=m%sz;
ll m1=cal(v,len2);
ll m2=cal(v,sz);
m1+=max(0ll,sm)*len1;
m2+=max(0ll,sm)*((len1>=)?(len1-):);
return max(m1,m2);
} int main(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int T,cas=;
scanf("%d",&T);
while(T--){
scanf("%lld%lld%lld%lld",&n,&s,&m,&k);
for(int i=;i<n;i++){
vis[i]=false;
scanf("%lld",&a[i]);
}
vec.clear();
ll ans=;
for(ll i=;i<n;i++){
if(!vis[i]){
vis[i]=true;
vec.push_back(i);
for(ll j=(k+i)%n;(j!=i)&&(!vis[j]);j=(j+k)%n){
vis[j]=true;
vec.push_back(j);
}
ans=max(ans,solve(vec));
vec.clear();
}
}
if(ans>s) ans=;
else ans=s-ans;
printf("Case #%d: %lld\n",cas++,ans);
} return ;
}