【填充——双指针，DP】

题目

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
char s[N];
bool check(int a, int b)
{
  if(s[a] == '?' || s[b] == '?') return true;
  if(s[a] == s[b]) return true;
  return false;
}
int main()
{
  cin >> s;
  int n = strlen(s);

  int i = 1, cnt = 0;
  while(i < n)
  {
    if(check(i-1, i)) {i += 2, cnt++;}
    else i += 1;
  }

  cout << cnt;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
char s[N];
int f[N];
bool check(int a, int b)
{
  if(s[a] == '?' || s[b] == '?') return true;
  if(s[a] == s[b]) return true;
  return false;
}
int main()
{
  cin >> s+1;
  int n = strlen(s+1);

  f[0] = f[1] = 0;
  for(int i = 2; i <= n; i++)
  {
    if(check(i-1, i)) f[i] = f[i-2] + 1;
    else f[i] = f[i-1];
  }

  cout << f[n];
}

若改成允许重叠，用动态规划解决

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int f[N][2];
char s[N];
int main()
{
    cin >> s + 1;

    f[1][0] = f[1][1] = 0;
    int n = strlen(s + 1);
    for (int i = 2; i <= n; i++)
    {
        if (s[i] == '?')
        {
            if (s[i - 1] == '0')
            {
                f[i][0] = f[i - 1][0] + 1;
                f[i][1] = f[i - 1][0];
            }
            else if (s[i - 1] == '1')
            {
                f[i][1] = f[i - 1][1] + 1;
                f[i][0] = f[i - 1][1];
            }
            else
            {
                f[i][1] = max(f[i - 1][1] + 1, f[i - 1][0]);
                f[i][0] = max(f[i - 1][0] + 1, f[i - 1][1]);
            }
        }
        else if (s[i] == '1')
        {
            f[i][1] = max(f[i - 1][1] + 1, f[i - 1][0]);
        }
        else if (s[i] == '0')
        {
            f[i][0] = max(f[i - 1][0] + 1, f[i - 1][1]);
        }
    }

    cout << max(f[n][0], f[n][1]);
    return 0;
}