本文主要是介绍Neko's loop HDU - 6444，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=6444
单调队列求有限制最大子段https://blog.csdn.net/sinat_34550050/article/details/52274141
先找出所有循环节 对于每个循环节 如果总权值为正 如果没有步数限制 那肯定是跑越多圈越好 但是最多m步 策略就需要调整了
一开始想的假设步数为m 循环节长度为len 那就绕m/len圈 再找一个m%len的最大子段 但并没有这么简单
比如m=23 len=11 循环节为1 1 1 1 1 1 -1 -1 -1 -1 -1 按这种策略就只有3 其实是7
所以最后一圈是不能想当然地走掉的 而要灵活处理 应该先绕(m-len)/len圈 再求m%len+len的最大子段
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
const ll N=0x3f3f3f3f3f3f3f3f;ll ary[10010],tmp[30010];
ll s;
int book[10010],que[30010];
int n,m,k,len;ll getmax(ll a,ll b)
{if(a>b) return a;else return b;
}ll getmin(ll a,ll b)
{if(a<b) return a;else return b;
}ll solveII(int lim)
{ll res;int i,head,tail;head=0,tail=0,res=0;//printf("***%d %d***\n",len,lim);//for(i=1;i<=3*len;i++) printf("*%lld*\n",tmp[i]);for(i=1;i<=3*len;i++){while(head<tail&&tmp[i-1]<tmp[que[tail-1]]) tail--;que[tail++]=i-1;while(head<tail&&i-que[head]>lim) head++;//printf("%lld %lld %lld*\n",res,tmp[i],tmp[que[head]]);res=getmax(res,tmp[i]-tmp[que[head]]);}return res;
}ll solveI()
{ll sum,gou;int i;sum=0;for(i=1;i<=len;i++) sum+=tmp[i];for(i=len+1;i<=3*len;i++) tmp[i]=tmp[i-len];for(i=1;i<=3*len;i++) tmp[i]+=tmp[i-1];if(sum>0){if(m>len){gou=((m-len)/len);return gou*sum+solveII(m%len+len);}else return solveII(m);}else return solveII(getmin(m,len));
}int main()
{ll ans;int t,cas,i,j;scanf("%d",&t);for(cas=1;cas<=t;cas++){scanf("%d%lld%d%d",&n,&s,&m,&k);for(i=0;i<n;i++) scanf("%lld",&ary[i]);memset(book,0,sizeof(book));memset(tmp,0,sizeof(tmp));ans=N;for(i=0;i<n;i++){j=i,len=0;if(book[j]==0){while(book[j]==0){tmp[++len]=ary[j];book[j]=1;j=(j+k)%n;}ans=getmin(ans,getmax(0ll,s-solveI()));}}printf("Case #%d: %lld\n",cas,ans);}return 0;
}/*
2
5 1000 5 1
1 1 -1 -1 1
5 1000 6 1
1 1 -1 -1 11
5 1000 5 1
1 1 -1 -1 11
5 1000 6 1
1 1 -1 -1 1
*/
这篇关于Neko's loop HDU - 6444的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
