dp practice_day 1

2023/3/5 Algorithm dp dp_practice_plan

今天就切了三道水题，别的时间都在写编译器

1.CF 1227C

水题，没啥好说的，每一个区间去求对应的方案数即可

void solve()
{
  int n,k;cin>>n>>k;
  string s;cin>>s;
  ll ans=0;
  unordered_set<char>st;
  for(int i=0;i<k;++i)
  {
    char c;cin>>c;
    st.insert(c);
  }
  int l=0,r=0;
  while(r<n)
  {
    while(r<n&&st.count(s[r]))++r;
    ll len=r-l;
    ans+=(len+1)*len/2;
    ++r;
    l=r;
  }
  cout<<ans<<'\n';
  return;
}

CF 467C

经典的区间dp，转移方程很好想，就是${dp[i][j]=max(dp[i][j],dp[i-m][j-1]+sum[i]-sum[i-])}$

void solve()
{
  int n,m,k;
  cin>>n>>m>>k;
  vector dp(n+1,vector<ll>(k+1));
  vector<ll>sum(n+1);
  for(int i=1;i<=n;++i)
  {
    cin>>sum[i];
    sum[i]+=sum[i-1];
  }
  for(int i=m;i<=n;++i)
  {
    for(int j=1;j<=k;++j)
    {
      dp[i][j]=dp[i-1][j];
      if(j*m>i)break;
      dp[i][j]=max(dp[i][j],dp[i-m][j-1]+sum[i]-sum[i-m]);
    }
  }
  cout<<dp[n][k]<<'\n';
  return;
}

CF 296B

容斥题，我们可以先预处理出对应位置上的3种不同情况和总情况数,即sa[i]==sb[i] sa[i]>=sb[i] sa[i]<=sb[i]，根据容斥定理，答案即为：

∏a[i] - ∏b[i] - ∏c[i] + ∏d[i]

至少有一对满足情况=所有情况 - 所有都不满足第一种- 所有都不满足第二种 + 两者交集

void solve()
{
  int n;cin>>n;
  string sa,sb;
  cin>>sa>>sb;
  vector<ll>a(n),b(n),c(n),d(n);//represent 1.the total number of situation 2. sa[i]>=sb[i] 3.sa[i]<=sb[i] 4. sa[i]==sb[i]
  // then the answer is A-B-C+D
  for(int i=0;i<n;++i)
  {
    if(sa[i]=='?'&&sb[i]=='?')
    {
        a[i]=100;
        b[i]=55;
        c[i]=55;
        d[i]=10;
    }
    else if(sa[i]=='?')
    {
        a[i]=10;
        b[i]=10-(sb[i]-'0');
        c[i]=sb[i]-'0'+1;
        d[i]=1;
    }
    else if(sb[i]=='?')
    {
        a[i]=10;
        c[i]=10-(sa[i]-'0');
        b[i]=sa[i]-'0'+1;
        d[i]=1;
    }
    else
    {
        a[i]=1;
        b[i]=(sa[i]>=sb[i]);
        c[i]=(sa[i]<=sb[i]);
        d[i]=(sa[i]==sb[i]);
    }
    if(i>0)
    {
        a[i]=(a[i]*a[i-1])%MOD;
        b[i]=(b[i]*b[i-1])%MOD;
        c[i]=(c[i]*c[i-1])%MOD;
        d[i]=(d[i]*d[i-1])%MOD;
    }
  }
  ll ans=a[n-1]-b[n-1]-c[n-1]+d[n-1];
  if(ans<0)ans+=MOD;
  cout<<ans<<'\n';
  return;
}

LOADING

dp practice_day 1