请求加强数据

Rtcya @ 2024-07-30 11:29:12

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn], dp[maxn];
int main() {
    int n, l, r;
    cin >> n >> l >> r;
    for (int i = 1; i <= n; i++) dp[i] = -2e9;
    cin >> a[0];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i <= n; i++) {
        for (int j = l; j <= r; j++) {
            if (i + j > n) dp[n + 1] = max(dp[n + 1], dp[i]);
            else {
                dp[i + j] = max(dp[i] + a[i + j], dp[i + j]);
            }
        }
    }
    cout << dp[n + 1] << endl;
}

by Rtcya @ 2024-07-30 11:35:24

更新，以下代码可以AC本题。。。 一眼O(N^2)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn], dp[maxn];
int main() {
    int n, l, r;
    cin >> n >> l >> r;
    for (int i = 1; i <= n + 1; i++) dp[i] = -2e9;
    cin >> a[0];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i <= n; i++) {
        for (int j = l; j <= r; j++) {
            if (i + j > n) {
                dp[n + 1] = max(dp[n + 1], dp[i]);
                break;
            }
            else {
                dp[i + j] = max(dp[i] + a[i + j], dp[i + j]);
            }
        }
    }
    cout << dp[n + 1] << endl;
}

by OrinLoong @ 2024-08-01 08:39:38

@Nano_core Cuball，我也拿O(N^2)做法过了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=2e5+5;
int N,L,R,A[MAXN],dp[MAXN],ans=0xb0b0b0b0;
int main(){
    scanf("%d%d%d",&N,&L,&R);
    for(int i = 0;i <= N;i++)scanf("%d",&A[i]);
    memset(dp,0xb0,sizeof(dp));
    dp[0]=0;
    for(int i = L;i <= N;i++){
        for(int j = max(0,i-R);j <= max(0,i-L);j++)dp[i]=max(dp[i],dp[j]+A[i]);
        //printf("dp[%d]:%d\n",i,dp[i]);
    }
    for(int i = max(0,N+1-R);i <= N;i++)ans=max(ans,dp[i]);
    printf("%d",ans);
    return 0;
}

by jiangzenyu @ 2024-08-06 09:01:51

@10circle

by jiangzenyu @ 2024-08-06 09:03:12

#include<cstdio>
int n,l,r,q,Inf=999999999;
int ans=-Inf,f[200009],dp[200009];
int qmax(int a,int b){
    return a>b?a:b;
}
int main(){
    scanf("%d%d%d",&n,&l,&r);
    for(int i=0;i<=n;i++){
        scanf("%d",&f[i]);
        dp[i]=-Inf;
    }
    dp[0]=0;
    for(int i=l;i<=n;i++)
        for(int j=qmax(0,i-r);j<=i-l;j++)
            dp[i]=qmax(dp[i],dp[j]+f[i]);
    for(int i=n-r+1;i<=n;i++) ans=qmax(ans,dp[i]);
    printf("%d",ans);
    return 0;
}

刚刚在灌水区看到的 c++98 + O2可过，这个做法显然是可以卡到O(n^2)的

by ZhangQirui1 @ 2024-08-07 21:37:14

哈哈我也是

#include <bits/stdc++.h>
using namespace std;
const int N=4*1e5+5;
int n,l,r,a[N];
int main()
{
  scanf("%d%d%d",&n,&l,&r);
  for(int i=0; i<=n; i++) scanf("%d",&a[i]);
  for(int i=n-l; i>=0; i--)
  {
    int s=-1e9;
    for(int j=l; j<=r; j++)
      s=max(s,a[i+j]);
    a[i]+=s;
  }
  printf("%d",a[0]);
  return 0;
}

真好又水过一道绿题

by xyz123 @ 2024-08-24 13:02:18

建议数据开到2e6+10或更大，卡掉线段树优化的办法

by xyz123 @ 2024-08-24 13:02:52

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int dp[N];
int a[N];
struct tree{
    int data[N<<2];
    void init(int k,int l,int r){
        if(l==r){
            data[k]=-0x3f3f3f3f;
            return;
        }
        int mid=(l+r)>>1;
        init(k<<1,l,mid);
        init(k<<1|1,mid+1,r);
        data[k]=-0x3f3f3f3f;
    }
    void update(int k,int l,int r,int x,int v){
        if(l==r){
            data[k]=v;
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid)  update(k<<1,l,mid,x,v);
        else    update(k<<1|1,mid+1,r,x,v);
        data[k]=max(data[k<<1],data[k<<1|1]);
    }
    int query(int k,int l,int r,int x,int y){
        if(l>y||r<x)    return -0x3f3f3f3f;
        if(l>=x&&r<=y)  return data[k];
        int mid=(l+r)>>1;
        return max(query(k<<1,l,mid,x,y),query(k<<1|1,mid+1,r,x,y));
    }
};
tree s;
int main(){
    int n,L,R;
    scanf("%d%d%d",&n,&L,&R);
    for(int i=0;i<=n;i++)   scanf("%d",&a[i]);
    s.init(1,0,n);
    s.update(1,0,n,0,a[0]);
    dp[0]=a[0];
    for(int i=L;i<=n;i++){
        int l=max(0,i-R),r=max(0,i-L);
        dp[i]=s.query(1,0,n,l,r)+a[i];
        s.update(1,0,n,i,dp[i]);
    }
    int ans=-0x3f3f3f3f;
    for(int i=max(0,n-R+1);i<=n;i++)    ans=max(ans,dp[i]);
    printf("%d\n",ans);
    return 0;
}

by EXR_FAL @ 2024-08-26 15:11:23

一眼单调队列优化，但n^2也能过，那我写单调队列的目的是什么。。。至少数据要到1e6吧。。

#include<bits/stdc++.h>
using namespace std;
int read(){
    int ans=0,flag=1;char ch=getchar();
    while('0'>ch || ch>'9'){if(ch=='-') flag=-1;ch=getchar();}
    while('0'<=ch && ch<='9'){ans=ans*10+ch-'0';ch=getchar();}
    return ans*flag;
}
const int N=2e6+114;
int n=read(),l=read(),r=read(),a[N],f[N],ans=INT_MIN;
int main(){
    for(int i=0;i<=n;i++) a[i]=read();   
    memset(f,-0x3f,sizeof f),f[0]=0;
    for(int i=l;i<=n+r-1;i++){
        for(int j=max(0,i-r);j<=i-l;j++) f[i]=max(f[i],f[j]+a[i]);
        if(i>=n) ans=max(ans,f[i]);
    }
    cout<<ans;
    return 0;
}

by a_round_thing @ 2024-08-27 15:34:24

+1,大体上是O(n^2)的，AC了

#include<bits/stdc++.h>
using namespace std;
const int N=200020;
int n,l,r;
int a[N];
int f[N];
int ans=-1e4;
int main(){
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++) cin>>a[i];
    memset(f,-0x3f,sizeof f);
    f[0]=a[0];
    for(int i=l;i<=n;i++){
        for(int j=i-r;j<=i-l;j++){
            if(j>=0) f[i]=max(f[i],f[j]);
        }
        f[i]+=a[i];
    }
//  for(int i=0;i<=n;i++) cout<<f[i]<<" ";
//  cout<<endl;
    for(int i=n;i>n-r;i--) ans=max(ans,f[i]);
    cout<<ans<<endl;
}