daily 2

2023/3/29 daily

CF 446A

思维，首先得判断一哈什么时候可以使用这个修改的条件，又不会让你丢掉本来的递增

我们用l[i]表示以i结尾的最长递增序列的长度

r[i]表示以i开头的最长递增子序列的长度

那么我们每次先判断当前最长(左/右)

然后再判断l[i-1]和r[i+1]能不能连城一片即可

void solve(){
  int n;
  cin>>n;
  vector<int>a(n+3),l(a),r(a);
  for(int i=1;i<=n;++i){
    cin>>a[i];
    if(i>1){
        if(a[i]>a[i-1]){
            l[i]=l[i-1]+1;
        }else{
            l[i]=1;
        }
    }else{
        l[i]=1;
    }
  }
  for(int i=n;i>=1;--i){
    if(i==n){
        r[i]=1;
    }else{
        if(a[i]<a[i+1]){
            r[i]=r[i+1]+1;
        }else{
            r[i]=1;
        }
    }
  }
  int ans=0;
  for(int i=1;i<=n;++i){
    ans=max(ans,max(l[i-1]+1,r[i+1]+1));
    if(a[i-1]+1<a[i+1]){
        ans=max(ans,l[i-1]+r[i+1]+1);
    }
  }
  cout<<ans<<'\n';
  return;
}

CF 453 B

分治，这个我觉得不太好想，但是看完题解感觉很直观，以后要多考虑这种分治的思想

void solve(){
  int n;
  cin>>n;
  vector<int>a(n);
  for(int i=0;i<n;++i)cin>>a[i];
  function<int(int,int)>paint=[&](int l,int r){
    int k=l;
    if(r<l)return 0;
    for(int i=l;i<=r;++i){
        if(a[i]<=a[k]){
            k=i;
        }
    }
    int subtract=a[k];
    for(int i=l;i<=r;++i){
        a[i]-=subtract;
    }
    return min(r-l+1,paint(l,k-1)+paint(k+1,r)+subtract);
  };
  cout<<paint(0,n-1)<<'\n';
  return;
}

腾讯阿里等三面了

蚂蚁字节在等二面

要是能去ob就好惹，待会健身上来好好看看ob的结构吧，干八楼！

LOADING

daily 2