[DP 字符串 计数去重]L3-020 至多删三个字符

[DP 字符串]L3-020 至多删三个字符

题目

思路

状态表示
集合

属性：count（不包含重复）
状态计算:
删除第i个或者不删除第i个

这题比较恶心的地方在于去重

aacdbb 删掉最后一个b和删除倒数第二个b是一样的

所以我们在删除第i个的时候要去重，去掉i前面的和第i位一样的（只要去1次就可以）

然后初始化的部分，递推过程中要直到上方和左上方

红色是没法删除的，所以绿色开始初始化

代码

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long LL;
typedef pair<int,int> PII;
//#define MULINPUT
/*DATA & KEY

*/
int T;
const int N=1E6+10;
char s[N];
LL f[N][4];
void solve(int C)
{
  //NEW DATA CLEAN
  
  //NOTE!!!
  cin>>s+1;
  int n=strlen(s+1);
  for(int i=1;i<=n;i++)f[i][0]=1;//
  for(int i=0;i<=3;i++)f[i][i]=1;//
  for(int i=1;i<=n;i++)
    for(int j=0;j<=3;j++)
    {
      if(i<j)break;
      f[i][j]=f[i-1][j];
      if(j>=1)f[i][j]+=f[i-1][j-1];
      
      for(int k=i-1;k>=1&&j>=i-k;k--)
      {
        if(s[k]==s[i])
        {
          f[i][j]-=f[k-1][j-(i-k)];
          break;
        }
      }
      
    }
  
  LL ans=0;
  for(int i=0;i<=3;i++)ans+=f[n][i];
  cout<<ans<<endl;
}

int main()
{
  #ifdef MULINPUT
    scanf("%d",&T);
    for(int i=1;i<=T;i++)solve(i);
  #else
    solve(1);
  #endif
  return 0;
}