随手加个传送门
其实题目都可以去vj看啊
TC250日常乱搞

简单地讨论一下

  • 如果前一个串是当前串的子串，那么可以选择不Undo，直接在后面输入（然而有时Undo一下更优2333，所以还要两种情况取min
  • Undo操作就是找一个最长的和它相同的前缀，这个用字典树可以轻易做到 
#include <bits/stdc++.h> using namespace std; const int N=2501; const int M=26; int trie[N][M]; int b[N]; int cnt; int n; template<class T> void checkmin(T &a,const T &b) { if (b<a) a=b; } template<class T> void checkmax(T &a,const T &b) { if (b>a) a=b; } class UndoHistory { public: int minPresses( vector <string> lines ) ; }; int insert(string s){ int x=0,ans=0; for(int i=0;i<s.size();i++){ if (!trie[x][s[i]-'a']){ trie[x][s[i]-'a']=++cnt; ans++; } x=trie[x][s[i]-'a']; //if (b[x]) ans=i+1; } //b[x]=1; return ans; } int is_sub(string s1,string s2){ if (s1.size()>s2.size()) return 0; for(int i=0;i<s1.size();i++) if (s1[i]!=s2[i]) return 0; return 1; } int UndoHistory::minPresses(vector <string> s) { n=s.size(); int ans=0; memset(b,0,sizeof b); for(int i=0;i<n;i++){ int mn=2e9; if (i>0&&is_sub(s[i-1],s[i])) mn=s[i].size()-s[i-1].size(); if (i==0) mn=s[i].size(); mn=min(mn,insert(s[i])+2); mn++; //cout<<mn<<endl; ans+=mn; //cout<<ans<<endl; } return ans; }