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.

发表评论

电子邮件地址不会被公开。 必填项已用*标注