CF1860D DP

lovelive__ · 2023-08-25 21:59:36 · 题解

CF1806D DP

• 题意：给你一个长为 n 的 0101 字符串，每次操作交换两个元素，求最少几次操作能使字符串的01对个数与10对个数相等。

• 题解：

  • 考虑为有两个字符串，就是要把s->t，t是01对10对差值为0的字符串。s与t不同的数量肯定是偶数，若是奇数，说明s与t中01数量不等。那么最小操作次数就是最小不同数量/2

  • 需要设计一个什么状态， 满足：

  • 所有状态可以表示（尤其是答案的状态）

  • 状态转移枚举的是什么（每一位放什么）

  • 转移

  • 01对与10对，考虑贡献，需要记录前面1的数量和sum_{01}-sum_{10}，状态呼之欲出dp[i][j][k]表示考虑前i个，有j个1，sum_{01}-sum_{10}的值为k时，s与dp状态表示的字符串最小差别数量。这个状态分法可以表示题目所需的条件。答案状态就是dp[n][cnt1][0]

  • 对于所有情况，下一位只需要枚举是0还是1，考虑下一位本身情况即可(倒着回去想，只能是前一位已经=j或则前一位=j-1这两个状态转移而来）。

  • 第i-1位已经放了j-1个1，第i位放置1，会带来+(i-1-(j-1))=+(i-j)也会带来-(cnt0-(i-j))那么dp[i][j][k]应由dp[i-1][j-1][k-cnt0+2*(i+j)]转移而来
  - 因为k可以去到$n^2/2$所以是$N^4$的

• 总结: 可以理解成两个字符串匹配，s是不变的，枚举t的所有状态，考虑t的状态与s产生的贡献

  void work() {
  string s;
  cin>>s;
  n = s.size();
  s = ' ' + s;
  int cnt0 = 0;
  vector<int> a(n+1);
  vector f(n+1, vector(2*(n*n)+10, INF ));
  for (int i=1; i<=n; i++)
      a[i] = (s[i] == '1'), cnt0+=!a[i];
  m = n*n/2;
  
  f[0][m] = 0;
  
  for(int i=1;i<=n;i++){
      for(int j=i;j>=0;j--){
          for(int k=-m;k<=m;k++){
              f[j][k+m]=f[j][k+m]+a[i];
  
              if(j && k+m+2*(i-j)-cnt0>=0) f[j][k+m]=min(f[j][k+m],f[j-1][k+m+2*(i-j)-cnt0]+(!a[i]));
          }
      }
  }
  
  if (f[n-cnt0][m] == INF) cout<<"-1\n";
  else cout<<f[n-cnt0][m]/2<<endl;
  }