HDU - 6444 Neko's loop(循环节+最大子段和)-白红宇

HDU - 6444 Neko's loop(循环节+最大子段和)

阅读量：6413 次

发布时间：2019-06-23

本文共 1675 字，大约阅读时间需要 5 分钟。

题意

一个有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 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   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
                   
                    #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 = 100000 + 10;const int maxm = 200000 + 10;const int mod = 1e9+7;ll n,m,s,k;vector
                    
                      vec;ll a[maxn],q[maxn],stk[maxn],sum[maxn];bool vis[maxn];ll cal(vector
                     
                       &v,ll tmp){ ll res=0; ll nn=v.size(); ll he=0,ta=0; for(ll i=0;i
                      
                       =sum[i]) ta--; stk[ta++]=i; } return res;}ll solve(vector
                       
                        &v){ ll sz=v.size(); ll sm=0; for(ll i=0;i
                        
                         =1)?(len1-1):0); return max(m1,m2);}int main(){#ifdef LOCAL freopen("in.txt", "r", stdin);// freopen("output.txt", "w", stdout);#endif int T,cas=1; scanf("%d",&T); while(T--){ scanf("%lld%lld%lld%lld",&n,&s,&m,&k); for(int i=0;i
                         
                          s) ans=0; else ans=s-ans; printf("Case #%d: %lld\n",cas++,ans); } return 0;}

转载于:https://www.cnblogs.com/fht-litost/p/9551047.html

你可能感兴趣的文章