hdu 6444 Neko's loop 单调队列优化DP

时间：2022-08-21 23:23:38

Neko's loop

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 356    Accepted Submission(s): 56

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
Source
Recommend
chendu

刚开始看 觉得是n^2的暴力 ，然后被蒋大佬说 必须O(n)过，最后在WA了四发以后，比赛最后半个小时A了这道题

n个数，最多跳m步，每次跳到（i+k）%n，然后求距 s 的最小差，大于s 计为0

很朴素的想法 枚举每个i从0到n-1 然后暴力跑循环节

假设循环节大小为len，最后 res = max(0, getRes(len)) *m/len + max(0, getRes(m%len)); getRes(x) 就是求一个循环节上 长度最大为x的最长子段和（注意是子段 不是子序列）

可以预处理O（n）求出每个循环节， 然后对每个循环节 求上面的结果

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <vector>

typedef long long ll;

using namespace std;

const int N = 1e4+;

int n,m,k,cnt ;

ll s, MAX, v[N];

bool vis[N]; vector<ll> g[N];

ll que[N<<],mx[N<<],sta[N<<];

ll solve(const vector<ll>&vv, int count) {

    int sz= vv.size();

    for(int i=;i<sz;i++)

        que[i] = que[i+sz] = vv[i];

    sz = sz<<;

    int st=,ed=;

    ll res=;

    for(int i=;i<sz;i++) {

        if(i==)

            mx[i] = que[i];

        else

            mx[i] = mx[i-]+que[i];

        if(i < count)

            res = max(res, mx[i]);

        while (st < ed && sta[st]+count < i)

            st++;

        if(st < ed)

            res = max(res, mx[i] - mx[sta[st]]);

        while (st < ed && mx[i] <= mx[sta[ed-]])

            ed--;

        sta[ed++]=i;

    }

    return res;

}

ll getRes(const vector<ll>& vv,int step,ll top) {

    ll mod = step % vv.size(); ll kk = step/ vv.size();

    ll sum = ;

    for(int i=; i<vv.size();i++)

        sum += vv[i];

    ll mx1 = solve(vv, mod);

    ll mx2 = solve(vv, vv.size());

    mx1 += max(0LL, sum)*kk;

    mx2 += max(0LL, sum)*((kk>)?kk-:);

    return max(mx1,mx2);

}

int main ()

{

    //freopen("in.txt","r",stdin);

    int T; scanf("%d",&T);

    for(int cas=; cas<=T; cas++) {

        memset(vis,,sizeof(vis));

        scanf("%d %lld %d %d", &n, &s, &m, &k);

        for(int i=;i<n;i++)

            scanf("%lld", &v[i]);

        cnt=; MAX=;

        for(int i=; i<n; i++) {

            g[cnt].clear();

            if(!vis[i]) {

                vis[i]=;

                g[cnt].push_back(v[i]);

                for(int j=(i+k)%n; j!=i && !vis[j]; j=(j+k)%n) {

                    g[cnt].push_back(v[j]);

                    vis[j]=;

                }

                //for(int j=0;j<g[cnt].size();j++)

                    //cout << g[cnt][j]<<" ";

                //cout <<endl;

                MAX = max(MAX, getRes(g[cnt], m, s));

                cnt++;

            }

        }

        if(MAX >= s) MAX=;

        else MAX = s-MAX;

        printf("Case #%d: %lld\n", cas, MAX);

    }

    return ;

}

相关文章