普及模考T2求解

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[200005],dp[200005],ans=-1;
signed main(){
  freopen("B.in","r",stdin);
  freopen("B.out","w",stdout);
  int t;
  cin>>t;
  while(t--){
	ans=-1;
    int n,l,r;
	cin>>n>>l>>r;
	for(int i=1;i<=n;i++){
      cin>>a[i];
    }
	memset(dp,1e10,sizeof 1e10);
	dp[1]=a[1];
	for(int i=2;i<=n;i++){
  	  for(int j=i-l;j>=max(0ll,i-r);j--){
        dp[i]=min(dp[i],max(a[i],dp[j]));
      }
	}
	for(int i=1;i<=n+r;i++){
      ans=max(ans,dp[i]);
      //cout<<dp[i]<<" ";
    }
	cout<<ans<<endl;
  }
  return 0;
}

使用动态规划算法,dp[i]是第i个位置上的最优解。

1 个赞

memset(dp,1e10,sizeof 1e10);
你在干什么

1 个赞

你的状态定义是不是出错了, 应该是以第i个数为结尾的最值吧

1 个赞

那么统计ans的时候不应该是在[n, n + r)这个区间统计的吗

1 个赞