题解 P1481 【魔族密码】

ChoHakuNe · 2017-10-14 13:19:44 · 题解

类似最长不下降子序列的一道dp

无非就是把判断大小换成判断前缀

f[i]表示[1,i]中到第i个单词的最大前缀数量

并不知道一些大佬为什么要用复杂的函数判断前缀，因为题目中说明不会有重复的单词，所以如果pos(a,b)=1，那么a就一定是b的前缀

然后就是十分老实的dp代码...

pas
program loubcomtuter;
var a:array[0..2001] of string;
    f:array[0..2001] of integer;
    n,i,j,max:integer;
begin
 readln(n);
 for i:=1 to n do f[i]:=1;//初始化，没有前缀的情况下长度为1
 for i:=1 to n do
  begin
   readln(a[i]);
   for j:=1 to i-1 do//因为按照字典顺序，之后的单词里一定没有a[i]的前缀
    if (pos(a[j],a[i])=1) and (f[j]>=f[i]) then inc(f[i]);//状态转移方程
  end;
  for i:=1 to n do if f[i]>max then max:=f[i];//f[n]不一定是最优解，找前缀数量最多的
 write(max);
end.