dp practice_day 4

CF 877B

依旧是先确认状态:

1.当前遍历到第几个字符

2.当前字符在哪一段中

之后是转移

1.当前字符为’a’,那么有三种情况
dp[i][0]=dp[i-1][0]+1
dp[i][1]=dp[i-1][1]
dp[i][2]=max(dp[i-1][1],dp[i-1][2])

2.当前字符为’b’,也有三种情况(经典废话
dp[i][0]=dp[i-1][0]
dp[i][2]=dp[i-1][2]
dp[i][1]=max(dp[i-1][0]+1,dp[i-1][1]+1)

void solve()
{
  string s;
  cin>>s;
  int n=s.size();
  vector dp(n,vector<ll>(3));
  dp[0][0]=dp[0][2]=s[0]=='a';
  dp[0][1]=s[0]=='b';
  for(int i=1;i<n;++i)
  {
    if(s[i]=='a'){
        dp[i][0]=dp[i-1][0]+1;
        dp[i][1]=dp[i-1][1];
        dp[i][2]=max(dp[i-1][1],dp[i-1][2])+1;
    }else{
        dp[i][1]=max(dp[i-1][0]+1,dp[i-1][1]+1);
        dp[i][0]=dp[i-1][0];
        dp[i][2]=dp[i-1][2];
    }
  }
  cout<<std::max({dp[n-1][0],dp[n-1][1],dp[n-1][2]})<<'\n';
  return;
}

今天全天都在写paging lab，感觉还是有点收获的，今天的dp训练就开摆了，明天把虚存和操作系统的东西给整理一下