codeforces 1197D-Yet Another Subarray Problem

怼烎@ 2023-06-05 12:44 75阅读 0赞

传送门:QAQQAQ

题意:给你一个序列,求一个子序列a[l]~a[r]使得该子序列的sum(l,r)-k*(r-l+1+m+1)/m值是在所有子序列中最大的,并输出最大值

思路:比赛的时候使用O(n)写的,但是被hack了,因为O(n)无法记录当前距离下一次-k还有多少,若用单调队列维护也不知道前面应该弹出多少(可能现在把前面弹出是最优的,但是到后面可能因为个数还没到m的倍数,把前面加进去又是最优的),所以我们考虑再加一维

法一:dp[i][j]表示序列到i截止,这一轮已经进行了j次取数(j=(len+m-1)%m),那么dp[i][j]维护的就是起点为s=i-j+1-m*t(t>=0)这个集合的最优,这样所有的dp[i][j]就可以维护以i截止的最优答案了

对于当前i更新有两种情况:第一种是只取当前这个a[i]这个在dp[i][1]特判即可

            第二种是还要取前面的,dp[i][j]从dp[i-1][j-1](因为dp[i-1][j-1]所维护的s集合和dp[i][j]所维护的s集合是一样的)转移即可(注意边界条件)

(之前HCY玄学又加了一层循环更新,一直看不懂,后来发现他虽然答案是对的,但m次更新中只有1次是有效的)

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std;
  6. typedef long long ll;
  7. const ll inf=200000000000000;
  8. int n,m;
  9. ll ans=0,dp[300005][20],sum[300005],a[300005],k;
  10. int main()
  11. {
  12. scanf("%d%d%lld",&n,&m,&k);
  13. for(int i=1;i<=n;i++)
  14. {
  15. scanf("%lld",&a[i]);
  16. sum[i]=sum[i-1]+a[i];
  17. }
  18. for(int i=1;i<=n;i++)
  19. {
  20. for(int j=0;j<=m;j++) dp[i][j]=-inf;
  21. }
  22. dp[1][1]=a[1]-k;
  23. for(int i=2;i<=n;i++)
  24. {
  25. dp[i][1]=a[i]-k;
  26. for(int j=1;j<=min(i,m);j++)
  27. {
  28. if(j==1) dp[i][j]=max(dp[i][j],dp[i-1][m]+a[i]-k);
  29. else dp[i][j]=max(dp[i][j],dp[i-1][j-1]+a[i]);
  30. }
  31. }
  32. for(int i=1;i<=n;i++)
  33. {
  34. for(int j=1;j<=m;j++) ans=max(ans,dp[i][j]);
  35. }
  36. cout<<ans<<endl;
  37. return 0;
  38. }//

法二:

和比赛时我的思路很像,只不过这里多加了一层维护start_point%m=rnd,进行m次尺取法即可(在时间够的情况下,搞不清楚当前单调队列弹出几个是最优的,那么就枚举,这样就不用担心前面要弹出什么了,只需在len%m=0时判断是否要把起始点重置即可)

即如果当前的和减去k*t小于0,那么就重新开始,否则继续加

注意ans在每一次向后扩展时都要更新

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=300005;
  5. ll ans=0,n,a[N],m,k;
  6. int main()
  7. {
  8. scanf("%lld%lld%lld",&n,&m,&k);
  9. for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
  10. for(int rnd=1;rnd<=m;rnd++)
  11. {
  12. ll len=0; ll now=0;
  13. for(int i=rnd;i<=n;i++)
  14. {
  15. if(len%m==0) if(now-len/m*k<0) now=0,len=0;
  16. now+=a[i]; len++;
  17. ans=max(ans,now-(len+m-1)/m*k);
  18. }
  19. }
  20. cout<<ans<<endl;
  21. return 0;
  22. }

转载于:https://www.cnblogs.com/Forever-666/p/11241525.html

发表评论

表情:
评论列表 (有 0 条评论,75人围观)

还没有评论,来说两句吧...

相关阅读