f[i,j,k]表示以i字母开头，长度为j，以k结尾的串有多少个 
f[i,j,k]+=f[i,j-1,p]  (1<=p<=k-1)
然后sum[i,j]表示以长度为i，开头为j的有多少个。

最后一步步加起来就可以了。

var
  s:string;
  f:array['a'..'z',1..10,'a'..'z']of longint;
  sum:array[0..10,'a'..'z']of longint;
  i,j,k,tmp,len,ans:longint;
  ch1,ch2,ch3,ch:char;

procedure init_judge;
  begin
    readln(s);
    for i:=2 to length(s) do
      if s[i]<=s[i-1] then
        begin
          writeln(0);
          halt;
        end;
  end;

procedure prework;
  begin
    for ch:='a' to 'z' do f[ch,1,ch]:=1;
    for ch1:='a' to 'z' do
      for len:=2 to 10 do
        for ch2:='a' to 'z' do
          for ch3:='a' to chr(ord(ch2)-1) do
            inc(f[ch1,len,ch2],f[ch1,len-1,ch3]);

    for len:=1 to 10 do
      for ch1:='a' to 'z' do
        for ch2:='a' to 'z'do
          inc(sum[len,ch1],f[ch1,len,ch2]);
  end;

procedure dawn;
  begin
    len:=length(s);
    for i:=1 to len-1 do
      for ch:='a' to 'z' do
        inc(ans,sum[i,ch]);
    for ch:='a' to chr(ord(s[1])-1) do
      inc(ans,sum[len,ch]);
    for i:=2 to len do
      for ch:=chr(ord(s[i-1])+1) to chr(ord(s[i])-1) do
        inc(ans,sum[len-i+1,ch]);
    inc(ans);
    writeln(ans);
  end;

begin
  init_judge;
  prework;
  dawn;
end.

• 也是DP，C++ (740) Idy002 2014-08-19 18:54:08