题解 P1410 【子序列】

courage · 2013-07-25 12:26:06 · 题解

这题乍一看毫无思路。显然不可能穷举长度为N/2的严格递增子序列。

不过联想到NOIP1999（普及组）的导弹拦截的第二问，就有思路了。这题其实与它的第二问差不多，只要算出该序列的最大非升子序列长度L，判断一下是否大于2即可。

1.假如L>2，显然一个严格递增子序列至多包含非升子序列的一个元素，2个子序列至多包含2个元素，故两个严格递增子序列不可能把原序列的每个元素都包含，所以输出No!

2.假如L<=2：

2.1若L=1，显然原序列严格递增，必能按照题意划分，输出Yes!

2.2若L=2，用反证法易得去除一个长度为2的非升子序列之后的序列严格递增。

因此，将这两个元素分别放到两个子序列里面，总能构造出两个严格递增的子序列。

代码：

var  
  a,f:array[1..2000] of longint;  
  n,m,i,j:longint;  
function max(a,b:longint):longint;  
begin  
  max:=a;  
  if a<b then max:=b;  
end;  
begin  
  while not eof do  
    begin  
      read(n);  
      for i:=1 to n do read(a[i]);  
      readln;  
      for i:=1 to n do  
        begin  
          f[i]:=1;  
          for j:=1 to i-1 do if a[i]<=a[j] then  
            f[i]:=max(f[i],f[j]+1);  
        end;  
      for i:=2 to n do if f[i]>f[1] then f[1]:=f[i];  
      if f[1]>=3 then writeln('No!') else writeln('Yes!');  
    end;  
end.