AcWing 1087. 修剪草坪

題意:

有n個(gè)數(shù)，不能選超過連續(xù)的k個(gè)數(shù)，問所能選的最大值是多少？

題解：

我們首先分析dp過程：
dp[i]表示選擇完前i個(gè)數(shù)的最大值
sum[i]表示前i項(xiàng)和
對(duì)于第i個(gè)數(shù)，它有兩個(gè)情況，選和不選
1.不選，dp[i]=dp[i-1]
2.選，那么以i為結(jié)尾的連續(xù)長(zhǎng)度可以為1，也可以為2。。。，我們?cè)O(shè)所選的連續(xù)長(zhǎng)度為j(1<=j<=k),那么這個(gè)區(qū)間就是[i-j+1,i]，而第i-j個(gè)數(shù)就不選，再往前的區(qū)間答案就是dp[i-j-1]
所以此時(shí)dp[i]=dp[i-j-1]+sum[i]-sum[i-j]
i是固定的，j是不固定的，所以我們將式子變下形
dp[i]=(dp[i-j-1]-sum[i-j]) +sum[i] = g[i-j]+sum[i]
令g[i]=dp[i-1]-sum[i],這樣我們要讓dp[i]最大，就要讓g[i-j]最大，單調(diào)隊(duì)列維護(hù)下降序列得到區(qū)間長(zhǎng)度為k的g[i]的最大值

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=1e5+9; ll f[maxn]; ll s[maxn]; int q[maxn]; ll g(int i){if(i==0)return 0;return f[i-1]-s[i]; } int main() {int n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>s[i];s[i]+=s[i-1];}int hh=0,tt=0;for(int i=1;i<=n;i++){if(q[hh]+k<i)hh++;f[i]=max(f[i-1],g(q[hh])+s[i]);while(hh<=tt&&g(q[tt])<=g(i))tt--;q[++tt]=i;}cout<<f[n];return 0; } /* dp[i]=dp[i-1] 當(dāng)我們選擇連續(xù)長(zhǎng)度為j時(shí)，(1<=j<=k) dp[i]=dp[i-j-1]+s[i]-s[i-j] */

總結(jié)

以上是生活随笔為你收集整理的AcWing 1087. 修剪草坪28的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。