dp practice day 9

CF 466C

判断一个数组能有几种划分方式让每个块都相等
首先判断前缀和是否是3的倍数
之后枚举分界点即可

void solve(){
  int n;cin>>n;
  vector<ll>sum(n+1);
  for(int i=1;i<=n;++i){
    cin>>sum[i];
    sum[i]+=sum[i-1];
  }
  if(sum[n]%3){
    cout<<0<<'\n';
    return;
  }
  ll ans=0,p1=0,opp=sum[n]/3;
  for(int i=1;i<n;++i){
    if(opp*2==sum[i]){
        ans+=p1;
    }
    if(opp==sum[i]){
        ++p1;
    }
  }
  cout<<ans<<'\n';
  return;
}

CF 650B

求多个数组的最长公共子序列
只需要保存每个数组的对应位置的数的位置信息即可，然后枚举第一个数组的子序列，转移就好了

void solve(){
  int n,k;cin>>n>>k;
  vector<vector<int>>pos(k+1,vector<int>(n+1)),a(pos);
  for(int i=1;i<=k;++i){
    for(int j=1;j<=n;++j){
      cin>>a[i][j];
      pos[i][a[i][j]]=j;
    }
  }
  vector<int>dp(n+1,1);
  int ans=0;
  for(int i=1;i<=n;++i){
    for(int j=1;j<i;++j){
      bool flag=true;
      for(int kk=2;kk<=k;++kk){
        if(pos[kk][a[1][i]]<=pos[kk][a[1][j]]){
          flag=false;
          break;
        }
      }
      if(flag){
        dp[i]=max(dp[i],dp[j]+1);
      }
    }
    ans=max(ans,dp[i]);
  }
  cout<<ans<<'\n';
  return;
}

CF 633D

树上DP，令dp[i][0/1]表示以i为根的数i所在的联通块是否有黑色点的方案数
那么转移如下，用乘法原理很好理解

$dp[x][0]=dp[v][0]*dp[x][0]+dp[v][1]*dp[x][0]$

$dp[x][1]=dp[x][1]*(dp[v][0]+dp[v][1])+dp[x][0]*dp[v][0]$

void solve(){
  int n;cin>>n;
  vector<vector<int>>E(n);
  for(int i=1;i<n;++i){
    int x;cin>>x;
    E[i].push_back(x);
    E[x].push_back(i);
  }
  vector<int>c(n);
  for(int i=0;i<n;++i)cin>>c[i];
  vector dp(n,vector<ll>(2));
  function<void(int,int)>dfs=[&](int x,int f){
    dp[x][c[x]]=1;
    for(int v:E[x]){
        if(v==f)continue;
        dfs(v,x);
        int dp0=dp[x][0],dp1=dp[x][1];
        dp[x][1]=(dp1*(dp[v][1]+dp[v][0])%MOD+dp0*dp[v][1]%MOD)%MOD;
        dp[x][0]=(dp[v][1]+dp[v][0])*dp[x][0]%MOD;
    }
  };
  dfs(0,-1);
  cout<<dp[0][1]<<'\n';
  return;
}

考完试了，明天开始背八股了,题也得继续写