本文主要是介绍jzoj_1371 假期，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
题意：
奶牛们可以放假了，假期可以在1~n天中选一段连续的，既不能大于q也不能小于p，每天都有一个享受值w，求它们在假期里最多能获得多少享受值。
思路：
用f[i][0]记录前缀和，之后的步骤和1370差不多，最后从[i+p-1...min(n,i+q-1)]中求出最大值并减去f[i-1][0]，因为这里用的是前缀和。
代码：
#include<cstdio>
#include<cmath>
long long ans,f[100001][20],x;//要用long long
int n,p,q;
long long max(long long x,long long y){return x>y?x:y;}
long long min(long long x,long long y){return x<y?x:y;}
long result(int x,int y)
{long long z=(long long)(log(y-x+1)/log(2));return max(f[x][z],f[y+1-(1<<z)][z]);
}
int main()
{scanf("%d%d%d",&n,&p,&q);for (int i=1;i<=n;i++)scanf("%lld",&f[i][0]),f[i][0]+=f[i-1][0];//f[i][0]存i的前缀和for (int j=1;1<<j<=n;j++) for (int i=1;i+(1<<j)-1<=n;i++){f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);//RMQ}ans=-2147483647;for (int i=1;i<=n-p+1;i++){ans=max(ans,result(i+p-1,min(n,i+q-1))-f[i-1][0]);//找最大值}printf("%lld",ans);
}这篇关于jzoj_1371 假期的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
