题解：[USACO11OPEN] Forgotten Password S

题解[USACO11OPEN] Forgotten Password S题解[[USACO11OPEN] Forgotten Password S](https://www.luogu.com.cn/problem/P3025)解题思路代码实现解题代码时间复杂度分析题解[USACO11OPEN] Forgotten Password S本文章同步发表于洛谷。解题思路这里的 除特殊说明外都表示字符串拼接。这题可以用 DP 做。设d p i dp_idpi​表示密码P PP从第一个字母开始到第i ii个字母可能的密码中字典序最小的那个密码。我们可以对于所有的i ii都判断一下每个单词j jj是否可以放到以第i ii个字符结尾的这个位置设单词j jj的长度为s i z j siz_jsizj​如果可以放就更新d p i dp_idpi​为d p i − s i z j j dp_{i-siz_j}jdpi−sizj​​j和d p i dp_idpi​之中字典序最小的那一个。代码实现中有几个细节需要注意如果d p i − s i z j dp_{i-siz_j}dpi−sizj​​为空并且i − s i z j ≠ 0 i-siz_j\ne0i−sizj​0的话是不能更新d p i dp_idpi​的因为d p i − s i z j dp_{i-siz_j}dpi−sizj​​是没有方案的。如果d p i dp_idpi​为空我们就不用判断d p i − s i z j j dp_{i-siz_j}jdpi−sizj​​j和d p i dp_idpi​哪个字典序更小直接更新d p i dp_idpi​。最后d p L dp_LdpL​即为答案。代码实现字符串比较我们可以使用string实现。解题代码#includebits/stdc.husingnamespacestd;intn,m;string s,w[1010],dp[1010];intsiz[1010];boolchk(intx,inty){if(x0)returnfalse;for(inti0;isiz[y];i)if(s[ix]!?s[ix]!w[y][i])returnfalse;// 判断编号为 y 的单词能不能放returntrue;}intmain(){cinnm;cins;s0s;for(inti1;im;i)cinw[i],siz[i]w[i].size();for(inti1;in;i){for(intj1;jm;j){// 判断能不能放在以 i 结尾的位置if(chk(i-siz[j]1,j)\(dp[i]||dp[i-siz[j]]w[j]dp[i])\(dp[i-siz[j]]!||i-siz[j]0))// 判断放完这个单词后字典序是不是变小了dp[i]dp[i-siz[j]]w[j];}}coutdp[n]endl;return0;}时间复杂度分析为避免歧义这里N W NWNW写作M MM。判断单词能不能放复杂度最高为O ( 20 ) \mathcal O(20)O(20)总的时间复杂度为O ( 20 × L M ) \mathcal O(20\times LM)O(20×LM)。