Poj1952 BUY LOW BUY LOWER — 最长下降子序列+统计不重复串个数

Note: 本文最初于 2011年03月24日 星期四 17:15 在 hi.baidu.com/lydrainbowcat 发表。šš

统计不重复串个数主要是累加个数时防止重复转移。

设读入数据存储于a[i]。

设f[i]、d[i]表示以a[i]结尾的最长下降子序列长度、不重复串个数。

f[i]按照平常方式转移即可。

每次计算出一个f[i]后倒着往前扫一遍，用v数组记录某个数是否已经遇到过。则d[i]的值就是所有的满足j<i，且f[j]+1=f[i]这个条件的的d[j]的总和。其中若有两个一样的数（a[j]=a[k]且f[j]+1=f[k]+1=f[i]）则只累加后边那个（可用贪心法证明）。

Source Code

Problem: 1952		User: lydliyudong
Memory: 972K		Time: 219MS
Language: Pascal		Result: Accepted

• Source Code

var
 a,f,d:array[0..5001]of longint;
 v:array[0..65537]of boolean;
 n,i,j:longint;
 flag:boolean;
begin
 readln(n);
 for i:=1 to n do read(a[i]);
 a[0]:=65537; a[n+1]:=-1;
 fillchar(f,sizeof(f),0);
 fillchar(d,sizeof(d),0);
 d[0]:=1;
 for i:=1 to n+1 do
  begin
   for j:=0 to i-1 do
    if (f[i]<f[j]+1)and(a[j]>a[i]) then f[i]:=f[j]+1;
   fillchar(v,sizeof(v),0);
   for j:=i-1 downto 0 do
    if (f[j]+1=f[i])and(a[j]>a[i])and not v[a[j]] then
     begin
      v[a[j]]:=true;
      inc(d[i],d[j]);
     end;
  end;
 writeln(f[n+1]-1,' ',d[n+1]);
end.