【hdu 6444】Neko's loop

给你一个序列. 你可以选择起点i。然后每次往右跳k次。得到下一个值a[i+k];。问你跳m次能得到的最大值ma是多少。如果>=s输出0 否则输出s-ma;

【题解】

最后肯定会形成gcd(n,k)个环的。对于每个环(长度为cnt。预处理出从1..2*cnt的前缀和C[2*cnt](当成链处理就好枚举它从起点i开始。然后考虑它会怎么走? 1.如果c[cnt]>0,temp1加上m/cnt*C[cnt],然后对于剩余的m%cnt次走的机会。求出c[i-1..i+m%cnt-1]这一段的最大值get_ma,减去c[i-1]就是剩余的m%cnt次能走出来的最大值了。即temp1+=get_ma-c[i-1]; temp = max(temp,temp1) 2.如果m>=cnt,那么还有一种可能,就是剩余的最后一圈留着不走完整圈,而只取一个最大的值,这个时候如果c[cnt]>0,temp2+=(m/cnt - 1)*C[cnt],然后我们还留了一圈,也即cnt次机会可以走则求出c[i-1..i+cnt-1]这一段的最大值get_ma2,然后再减去c[i-1]就是剩余的cnt次能走出来的最大值了,即temp2+=get_ma2-C[i-1] temp = max(temp,tepm1) 对于每个起点i。都求出temp1,tepm2 最后return temp 就是当前这个环上走m次能得到的最大值了。枚举所有的环取最大的temp就是答案了

【代码】


#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1e4;
const int M = 15;

int n,m,k;
LL s;
int a[N+10],b[N*2+10],cnt;
LL c[N*2+10],mi[N*2+10][M+5];
int vis[N+10];

LL get_ma(int l,int r){
    int len = r-l+1;
    len = log2(len);
    return max(mi[l][len],mi[r-(1<<len)+1][len]);
}

LL ok(){
     c[0] = 0;
    for (int i = 1;i <= cnt;i++)
        c[i] = b[i],c[i+cnt] = b[i];
    for (int i = 1;i <= 2*cnt;i++) c[i]+=c[i-1];
    for (int i = 0;i <= 2*cnt;i++) mi[i][0] = c[i];
    for (int L = 1;L<=M;L++)
        for (int i = 0;i <= 2*cnt;i++){
            if (i+(1<<L)-1>2*cnt) break;
            mi[i][L] = max(mi[i][L-1],mi[i+(1<<(L-1))][L-1]);
        }
    LL temp = 0;
    for (int i = 1;i <= cnt;i++){
        LL temp1 = 0;
        //第一种情况.
        //如果环的和大于0就尽量用
        if (c[cnt]>0) temp1 += 1LL*m/cnt*c[cnt];
        int rest = m%cnt;
        if (rest>0) temp1+=get_ma(i-1,i+rest-1)-c[i-1];

        LL temp2 = 0;
        //第二种情况
        //留cnt个
        if (m>=cnt){
            if (c[cnt]>0) temp2 += 1LL*(m-cnt)/cnt*c[cnt];
            temp2+=get_ma(i-1,i+cnt-1)-c[i-1];
        }
        temp = max(temp,temp1);
        temp = max(temp,temp2);
    }
    return temp;
}

int main()
{
    //freopen("D:\rush.txt","r",stdin);
    ios::sync_with_stdio(0),cin.tie(0);
    int T;
    cin >> T;
    int kk = 0;
    while (T--){
        cin >> n >> s >> m >> k;
        for (int i = 1;i <= n;i++) cin >> a[i];
        for (int i = 1;i <= n;i++) vis[i] = 0;
        LL ans = 0;
        for (int i = 1;i <= n;i++)
            if (vis[i]==0){
                cnt = 0;
                for (int j = i;vis[j]==0;j = (j+k)>n?(j+k-n):j+k){
                    cnt++;
                    b[cnt] = a[j];
                    vis[j] = 1;
                }
                ans = max(ans,ok());
            }
        cout<<"Case #"<<++kk<<": ";
        if (s<ans)
            cout<<0<<endl;
        else
            cout<<s-ans<<endl;
    }
    return 0;
}