题目https://codeforces.com/gym/297792/problem/D 题意：规定子序列【l,r】的花费为 求出这个数组的最大花费。
最初的思路：一开始采用的方法是定义一个node保存区间，求出每一个长度为l的区间的相加最大值，以及对应的左右端点，并保存到add数组中。用尺取的方法更新每一个add【i】。最后对于add中的每一个长度求出它的花费，取最大值即可。 这种思路是正确的，但是很遗憾尺取的时间开销太大了，直接超时。 错误代码如下：
#include <bits/stdc++.h> #include <algorithm> #include<iostream> #include <stdio.h> #define INF 0x3f3f3f3f const int maxn=300005; using namespace std; typedef long long ll; ll a[maxn]; ll pre[maxn]; //int vis[maxn]; struct node{ ll l,r; ll sum; }add[maxn]; int main(){ ll n,m,k; cin>>n>>m>>k; pre[0]=0; a[0]=0; for(ll i=1;i<=n;i++){ cin>>a[i]; pre[i]=pre[i-1]+a[i]; } add[n].sum=pre[n]; add[n].l=1; add[n].r=n; for(ll i=n-1;i>=1;i--){ ll left=1; ll right=left+i-1; ll sum=pre[right]; add[i].sum=sum; while(right<=n){ sum-=a[left]; left++; right++; sum+=a[right]; add[i].sum=max(add[i].sum,sum); } } ll sum=0; ll ans=0; for(ll i=1;i<=n;i++){ ll cushu=(i-1)/m+1; sum=add[i].sum-k*cushu; ans=max(sum,ans); } cout<<ans<<endl; return 0; }然后看了题解发现这个可以用dp做，其实就是一个背包dp，用dp[i][j]表示以i为右边界，连续j个的最大值，dp[i][j]=dp[i-1][j-1]，当j为0的时候就相当于新的一个m长度段，此时可能是开始，或者上一个m长度段减去k那么j==0时，dp[i][j]=max(a[i]-k,dp[i-1][m-1]+a[i]-k);最后的答案就是所有dp的值的最大值。
代码：
#include <bits/stdc++.h> #include <algorithm> #include<iostream> #include <stdio.h> #define INF 0x3f3f3f3f const int maxn=300005; using namespace std; typedef long long ll; ll a[maxn]; ll dp[maxn][20]; int main(){ ll n,m,k; cin>>n>>m>>k; for(int i=1;i<=n;i++) cin>>a[i]; ll ans=0; for(ll i=1;i<=n;i++){ for(ll j=0;j<min(i,m);j++){ if(j==0) dp[i][j]=max(a[i]-k,dp[i-1][m-1]+a[i]-k); else dp[i][j]=dp[i-1][j-1]+a[i]; ans=max(ans,dp[i][j]); } } cout<<ans<<endl; return 0; }