dp practice_day 2

今天具体做了一道区间dp，一道分组背包，一道树形dp

1. CF 362C

首先读懂题意，这就是冒泡排序的一轮而已,那么很显然，逆序对的数量就是需要交换的数量，然后，对于一次交换i和j,对总的逆序对的影响为

总的=原本总的+[i,j]内比a[i]大的数+[i,j]内比a[j]小的数-[i,j]内比a[i]小的数-[i,j]内比a[j]大的数

注意我们加减的时候直接取[i][j]就可以了，如果[i+1][j-1]什么的会越界

void solve()
{
  int n;cin>>n;
  vector<int>a(n+1);
  int maxi=0;
  for(int i=1;i<=n;++i)
  {
    cin>>a[i];
    maxi=max(a[i],maxi);
  }
  vector gt(n+1,vector<int>(n+1)),lt(gt);
  for(int i=1;i<=n;++i)
  {
    for(int j=1;j<=n;++j)
    {
        if(a[i]>a[j])
        {
            gt[i][j]++;
        }
        gt[i][j]+=gt[i][j-1];
        if(a[i]<a[j])
        {
            lt[i][j]++;
        }
        lt[i][j]+=lt[i][j-1];
    }
  }
  int ori=0,cnt=0,ans;
  for(int i=1;i<=n;++i)
  {
    ori+=gt[i][n]-gt[i][i];
  }
  ans=ori;
  for(int i=1;i<=n;++i)
  {
    for(int j=i+1;j<=n;++j)
    {
        int tmp=ori;
        tmp+=gt[j][j]-gt[j][i];
        tmp-=gt[i][j]-gt[i][i];
        tmp+=lt[i][j]-lt[i][i];
        tmp-=lt[j][j]-lt[j][i];
        if(tmp<ans)
        {
            ans=tmp;
            cnt=0;
        }
        if(tmp==ans){
            ++cnt;
        }
    }
  }
  cout<<ans<<' '<<cnt<<'\n';
  return;
}

1. CF 148E

第一眼看上去确实很像分组背包，那么考虑对应的求法，我们只需要预处理出每行对应数量的最大价值，然后套分组背包的板子即可，注意分组背包要先枚举容量再枚举物品

void solve()
{
  int n,m;cin>>n>>m;
  vector<vector<int>>ori(n+1);
  vector<vector<ll>>sum(n+1);
  for(int i=1;i<=n;++i)
  {
    int k;cin>>k;
    ori[i].resize(k+1);
    sum[i].resize(k+2);
    for(int j=1;j<=k;++j)
    {
        cin>>ori[i][j];
        sum[i][j]+=sum[i][j-1]+ori[i][j];
    }
  }
    vector pre_get(n+1,vector<int>(101));
    //pre calculate
    for(int i=1;i<=n;++i)
    {
      int len=ori[i].size();
      for(int j=1;j<len;++j)
      {
        ll tmp=0;
        for(int l=0;l<=j;++l)
        {
          int r=len-(j-l);
          tmp=max(tmp,sum[i][l]+sum[i][len-1]-sum[i][r-1]);
        }
        pre_get[i][j]=tmp;
      }
    }
    vector<ll>dp(m+1);
    for(int i=1;i<=n;++i)//pay attention to iteration order
    {
      for(int v=m;v>=0;--v)
      {
         for(int j=0;j<ori[i].size();++j)
         {
            if(v>=j)
            {
              dp[v]=max(dp[v],dp[v-j]+pre_get[i][j]);
            }
         }
      }
    }
    cout<<dp[m]<<'\n';
  return;
}

1. CF 533B

树型dp板子题，首先我们让dp[i][1/0]表示以i为根的子树，其节点数量为奇/偶的最大价值，那么考虑转移，很显然当前节点的奇数个节点的解可以由子节点的奇数/偶数转移。

需要注意的一点是，由于此题限制了节点数量为偶数，那么在进入搜索的时候需要把dp[i][1]设置为-INF

最终答案为dp[1][1] (包括了1)

void solve()
{
  int n;cin>>n;
  vector<ll>a(n+1);
  vector<vector<int>>E(n+1);
  for(int i=1;i<=n;++i)
  {
    int fa;cin>>fa>>a[i];
    if(fa!=-1)
    {
      E[fa].push_back(i);
    }
  }
  vector dp(n+1,vector<ll>(2));
  function<void(int)>dfs=[&](int now)
  { 
      dp[now][1]=-INF;
      if(E[now].size()==0)
      {
        dp[now][1]=a[now];
        dp[now][0]=0;
        return;
      }
      for(int v:E[now])
      {
        dfs(v);
        ll v0=dp[now][0],v1=dp[now][1];
        dp[now][1]=max(dp[v][1]+v0,dp[v][0]+v1);
        dp[now][0]=max(dp[v][1]+v1,dp[v][0]+v0);
      }
      dp[now][1]=max(dp[now][1],dp[now][0]+a[now]);
  };
  dfs(1);
  cout<<dp[1][1]<<'\n';
  return;
}

下午把lsm的sst写了，然后开始投国内简历吧，找实习真的太难顶惹