【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;

}

巴特西

【hdu 6444】Neko's loop

最新文章

热门文章