题目链接: https://codeforces.com/problemset/problem/1197/D
题意:
给你一个序列, 求一个子序列 a[l]~a[r] 使得该子序列的 sum(l,r)-k*(r-l+1)/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 集合是一样的) 转移即可 (注意边界条件)
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- using namespace std;
- typedef long long ll;
- const ll inf=200000000000000;
- int n,m;
- ll ans=0,dp[300005][20],sum[300005],a[300005],k;
- int main()
- {
- scanf("%d%d%lld",&n,&m,&k);
- for(int i=1;i<=n;i++)
- {
- scanf("%lld",&a[i]);
- sum[i]=sum[i-1]+a[i];
- }
- for(int i=1;i<=n;i++)
- {
- for(int j=0;j<=m;j++) dp[i][j]=-inf;
- }
- dp[1][1]=a[1]-k;
- for(int i=2;i<=n;i++)
- {
- dp[i][1]=a[i]-k;
- for(int j=1;j<=min(i,m);j++)
- {
- if(j==1) dp[i][j]=max(dp[i][j],dp[i-1][m]+a[i]-k);
- else dp[i][j]=max(dp[i][j],dp[i-1][j-1]+a[i]);
- }
- }
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++) ans=max(ans,dp[i][j]);
- }
- cout<<ans<<endl;
- return 0;
- }
法二: 尺取法
多加了一层维护 start_point%m=rnd, 进行 m 次尺取法即可
(在时间够的情况下, 搞不清楚当前单调队列弹出几个是最优的, 那么就枚举, 这样就不用担心前面要弹出什么了, 只需在 len%m=0 时判断是否要把起始点重置即可)
即如果当前的和减去 k*t 小于 0, 那么就重新开始, 否则继续加
注意 ans 在每一次向后扩展时都要更新
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N=300005;
- ll ans=0,n,a[N],m,k;
- int main()
- {
- scanf("%lld%lld%lld",&n,&m,&k);
- for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
- for(int rnd=1;rnd<=m;rnd++){
- ll len=0; ll now=0;
- for(int i=rnd;i<=n;i++){
- if(len%m==0) if(now-len/m*k<0) now=0,len=0;
- now+=a[i]; len++;
- ans=max(ans,now-(len+m-1)/m*k);
- }
- }
- cout<<ans<<endl;
- return 0;
- }
法三: 前缀和
我们可以发现 m 很小, 只有 10, 而当子段长度能整除以 m 的时候, 再添加一个才会使得我们多去减一个 k
我们可以让所有位置对 m 取模, 分成 0-m-1 这样的剩余系, 我们枚举剩余系, 以剩余系中的位置作为结尾求最大值
当我们枚举到剩余系 i 的时候, 我们另所有处于剩余系 i 的位置上的数 -k, 之后我们直接扫一遍序列, 不断累加并和 0 求最大值, 遇到可结束位置时, 与答案取最大值并更新答案
这样子我们可以再 O(nm) 的时间复杂度下做出这道题
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int maxn = 3e5+5;
- int n,m,k,a[maxn],b[maxn];
- int main(){
- cin>>n>>m>>k;
- for(int i=1;i<=n;i++)
- cin>>a[i];
- ll ans=0,s=0;
- for(int j=0;j<m;j++){
- for(int i=1;i<=n;i++)
- if(i%m==j)
- b[i]=a[i]-k;
- else
- b[i]=a[i];
- s=0;
- for(int i=1;i<=n;i++){
- s=max(s+b[i],0ll);
- if(i%m==j)
- ans=max(ans,s);
- }
- }
- cout<<ans<<endl;
- return 0;
- }
参考:,
[题解]Yet Another Subarray Problem-DP , 思维 (codeforces 1197D)
来源: http://www.bubuko.com/infodetail-3141899.html