题解 P7296 【[USACO21JAN] Uddered but not Herd G】

· · 题解

Uddered but not Herd 题解

之前交错题解区了

神仙状压dp，赛时联想到状压的时候简直惊了。以后自己出题也会往这个方面想了

发现如果某个字母没有在他听到的东西内出现，那么这个字母毫无意义。同理，如果一个字母出现过，那么他必然有意义。

于是，题目转化为求一个子串，每次让这个子串跟给出的字符串进行匹配，求最小的匹配次数。

没思路？看一眼数据范围，发现刚刚好有6个字母不需要用。一共个 26 字母，6个不用，算下来只用计算20个字母。符合范围的好像只有状压了。

设当前的子串为 ch， 考虑在子串后面加入字母算贡献。发现每个字母都是独立的。换言之，不论之前子串的顺序如何，这个字母跟之前子串中的字母产生的贡献都相等。如果在字符串中当前字母前一个位置的字母在子串出现过，那么加入这个字母一定会使最终朗诵次数减少一次。

枚举二元组暴力预处理出当子串存在字母 i，目前要加入字母 j 时的贡献，然后状压一下，每次加字母时积累贡献即可。字母要离散一下。答案即为 n - 贡献

赛时写的方法是 O(k^2n + k^2\times 2^k) 的，但应该可以通过一些状压上的小优化做到 O(k^2n + k\times 2^k)

代码只放主函数，需要全部代码的私戳

signed main(){
  cin >> ch;
  int n = ch.size();
  For(i,0,ch.size()-1) {
    pos[i+1] = (int)(ch[i]-'a')+1;
    mp[pos[i+1]] = true;
  }
  For(i,1,26) if (mp[i]) head[i] = ++tot;
  For(i,1,n) pos[i] = head[pos[i]];//简单的离散,懒人直接用 map 瞎弄了
  //pref i j : 在字母 i 前一位的字母 j 数量
  For(i,1,tot){
    For(j,1,tot){
      int v = 0,tmp = 0;
      For(k,1,n)if (pos[k]==i && pos[k-1]==j) tmp++;
      pref[i][j]=  tmp;
    }
  }
  For(i,1,1<<tot){
    For(j,1,tot){
      if ((i>>(j-1)) & 1) continue;
      int tmp = 0;
      For(k,1,tot) if ((i>>(k-1))&1) tmp += pref[j][k];//将所有贡献累计
      dp[i+(1<<(j-1))] = chkmax(dp[i+(1<<(j-1))],dp[i]+tmp);//转移
      ans = chkmax(ans,dp[i+(1<<(j-1))]);//人懒,不想去想最终状态,直接取max了
    }
  }
  cout << n-ans;
}