[题解]Yet Another Subarray Problem-DP 、思维（codeforces 1197D）

题目链接：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=;

 int n,m;

 ll ans=,dp[][],sum[],a[],k;

 int main()

 {

     scanf("%d%d%lld",&n,&m,&k);

     for(int i=;i<=n;i++)

     {

         scanf("%lld",&a[i]);

         sum[i]=sum[i-]+a[i];

     }

     for(int i=;i<=n;i++)

     {

         for(int j=;j<=m;j++) dp[i][j]=-inf;

     }

     dp[][]=a[]-k;

     for(int i=;i<=n;i++)

     {

         dp[i][]=a[i]-k;

         for(int j=;j<=min(i,m);j++)

         {

             if(j==) dp[i][j]=max(dp[i][j],dp[i-][m]+a[i]-k);

             else dp[i][j]=max(dp[i][j],dp[i-][j-]+a[i]);

         }

     }

     for(int i=;i<=n;i++)

     {

         for(int j=;j<=m;j++) ans=max(ans,dp[i][j]);

     }

     cout<<ans<<endl;

     return ;

 }

法二：尺取法

多加了一层维护 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=;

 ll ans=,n,a[N],m,k;

 int main()

 {

     scanf("%lld%lld%lld",&n,&m,&k);

     for(int i=;i<=n;i++) scanf("%lld",&a[i]);

     for(int rnd=;rnd<=m;rnd++){

         ll len=; ll now=;

         for(int i=rnd;i<=n;i++){

             if(len%m==) if(now-len/m*k<) now=,len=;

             now+=a[i]; len++;

             ans=max(ans,now-(len+m-)/m*k);

         }

     }

     cout<<ans<<endl;

     return ;

 }

法三：前缀和

我们可以发现 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+;

 int n,m,k,a[maxn],b[maxn];

 int main(){

     cin>>n>>m>>k;

     for(int i=;i<=n;i++)

         cin>>a[i];

     ll ans=,s=;

     for(int j=;j<m;j++){

         for(int i=;i<=n;i++)

             if(i%m==j)

                 b[i]=a[i]-k;

             else

                 b[i]=a[i];

         s=;

         for(int i=;i<=n;i++){

             s=max(s+b[i],0ll);

             if(i%m==j)

                 ans=max(ans,s);

         }

     }

     cout<<ans<<endl;

     return ;

 }

参考：https://www.cnblogs.com/Forever-666/p/11241525.html、http://blog.leanote.com/post/icontofig/Educational-Codeforces-Round-69

巴特西

[题解]Yet Another Subarray Problem-DP 、思维（codeforces 1197D）

最新文章

热门文章