daily 2

2023/4/9 daily

两道水题的一天捏，最近越来越懒了，主要是在这里等offer精神内耗，有点难绷，哎,正事一件不干

CF 340D

最长上升子序列板子题

void solve(){
  int n;
  cin>>n;
  vector<int>a(n);
  vector<int>opt;
  for(int i=0;i<n;++i){
    cin>>a[i];
    if(opt.size()==0||a[i]>=opt.back()){
        opt.push_back(a[i]);
    }else{
        int pos=lower_bound(opt.begin(),opt.end(),a[i])-opt.begin();
        opt[pos]=a[i];
    }
  }
  cout<<opt.size()<<'\n';
  return;
}

CF 358D

dp[i][0/1]表示第i个在i-1之后/之前拿

void solve(){
  int n;
  cin>>n;
  vector<int>a(n+1),b(a),c(a);
  vector<vector<int>>dp(n+2,vector<int>(2));//dp[i][0]means i feed after i-1
  for(int i=1;i<=n;++i)cin>>a[i];
  for(int i=1;i<=n;++i)cin>>b[i];
  for(int i=1;i<=n;++i)cin>>c[i];
  dp[1][0]=-INF;
  dp[1][1]=0;
  for(int i=2;i<=n+1;++i){
    dp[i][0]=max(dp[i-1][0]+b[i-1],dp[i-1][1]+a[i-1]);
    dp[i][1]=max(dp[i-1][1]+b[i-1],dp[i-1][0]+c[i-1]);
  }
  cout<<dp[n+1][0]<<'\n';
  return;
}

应该已经休息好了，明天，开始做人惹！

LOADING

daily 2